插入排序算法是較冒泡排序和選擇排序性能要更好的排序算法 插入排序的主要思想：將一組無序數分成兩個區，一個為有序區，另一個為無序區。從無序區中每次抽取一個數插入到有序中合適的位置。直至所有數全部有序 演示：（從小到大） 原始序列： 5 2 4 8 6 將序列分為有序區和無序區： 5 為有序區（紅色）， 2 4 8 6 為無序區（綠色） 即 5 2 4 8 6 開始： 每一次都由無序區中從左至右逐個抽取並放置到有序區的合適位置 首先抽取2 第一次插入結果為： 2 5 4 8 6 （2由於比5小，當然插入到其前面的位置上） 繼續抽取4 第二次插入結果為：2 4 5 8 6 （4比5小，但比2大，就插入到其兩者之間） 繼續抽取8 第三次插入結果為：2 4 5 8 6 （8比5大，所以不用移動，從這裡可以看出，無序區的數插入有序中的比較條件就是與有序區最尾的數進行比較即可） 繼續抽取6 第四次插入結果為：2 4 5 6 8 （到這裡，整個序列已經是一個有序的序列） 注意：插入數據的時候，位於插入數據右側的數都需要向後移動一位，因為這樣才能有位置進行插入。屬於這種情況的序列是存儲在一段連續的內存空間（例如數組）。但如果不是一段連續的內存空間（例如鏈表）就會簡單和高效些。 按照這種排序思路，可以明顯看出這個排序的好處就是增量排序 什麼是增量排序？其實很簡單：向一個已有序的序列中添加元素，並且要保證添加元素後的序列仍保持其原來的有序性 可見，這種插入排序算法在添加元素的時候，最多只需要遍歷一次即可。即O(n) 注意：這個不是最壞情況和平均情況的時間復雜度 插入排序最壞情況和平均情況的時間復雜度都是：O(n²) 代碼： [cpp] #include <stdio.h> void swap(int *a, int *b); int main() { int a[10] = {888,996,4548,181,45,0,1,418,61,48}; int i, j; int temp;//存放待插入的數 for (i = 1; i < 10; i++) { j = i; if (a[j] > a[j-1]) { temp = a[j]; while (j > 0 && temp > a[j-1]) { a[j] = a[j-1]; j--; } a[j] = temp; } } for (i = 0; i < 10; i++) { printf("%d\n", a[i]); } return 0; } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }
