直接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入完成為止。
設數(shù)組為a[0…n-1]。
1. 初始時，a[0]自成1個有序區(qū)，無序區(qū)為a[1..n-1]。令i=1
2. 將a[i]并入當前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間。
3. i++并重復第二步直到i==n-1。排序完成。
下面給出嚴格按照定義書寫的代碼（由小到大排序）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void Insertsort1(int a[], int n) { int i, j, k; for (i = 1; i < n; i++) { //為a[i]在前面的a[0...i-1]有序區(qū)間中找一個合適的位置 for (j = i - 1; j >= 0; j--) if (a[j] < a[i]) break; //如找到了一個合適的位置 if (j != i - 1) { //將比a[i]大的數(shù)據(jù)向后移 int temp = a[i]; for (k = i - 1; k > j; k--) a[k + 1] = a[k]; //將a[i]放到正確位置上 a[k + 1] = temp; } } } |
這樣的代碼太長了，不夠清晰。現(xiàn)在進行一下改寫，將搜索和數(shù)據(jù)后移這二個步驟合并。即每次a[i]先和前面一個數(shù)據(jù)a[i-1]比較，如果a[i] > a[i-1]說明a[0…i]也是有序的，無須調(diào)整。否則就令j=i-1,temp=a[i]。然后一邊將數(shù)據(jù)a[j]向后移動一邊向前搜索，當有數(shù)據(jù)a[j]<a[i]時停止并將temp放到a[j + 1]處。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void Insertsort2(int a[], int n) { int i, j; for (i = 1; i < n; i++) if (a[i] < a[i - 1]) { int temp = a[i]; for (j = i - 1; j >= 0 && a[j] > temp; j--) a[j + 1] = a[j]; a[j + 1] = temp; } } |
再對將a[j]插入到前面a[0…j-1]的有序區(qū)間所用的方法進行改寫，用數(shù)據(jù)交換代替數(shù)據(jù)后移。如果a[j]前一個數(shù)據(jù)a[j-1] > a[j]，就交換a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。這樣也可以實現(xiàn)將一個新數(shù)據(jù)新并入到有序區(qū)間。
|
1
2
3
4
5
6
7
|
void Insertsort3(int a[], int n) { int i, j; for (i = 1; i < n; i++) for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) Swap(a[j], a[j + 1]); } |
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://blog.csdn.net/morewindows/article/details/6665714
