直接插入排序?
1 排序思想：
將待排序的記錄Ri插入到已經(jīng)排好序的記錄R1，R2，……，R（N-1）中。
對(duì)于一個(gè)隨機(jī)序列而言，就是從第二個(gè)元素開始，依次將這個(gè)元素插入到它之前的元素中的相應(yīng)位置。它之前的元素已經(jīng)排好序。
第1次排序：將第2個(gè)元素插入到前邊的有序列表（此時(shí)前邊只有一個(gè)元素，當(dāng)然是有序的），之后，這個(gè)序列的前2個(gè)元素就是有序的了。
第2次排序：將第3個(gè)元素插入到前邊長(zhǎng)度為2的有序列表，使得前2個(gè)元素是有序的。
以此類推，直到將第N個(gè)元素插入到前面長(zhǎng)度為（N-1）的有序列表中。
2 算法實(shí)現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
// 直接插入排序void straight_insert_sort(int num[], int len){ int i,j,key; for(j=1;j<len;j++){ key=num[j]; i=j-1; while(i>=0&&num[i]>key){ num[i+1]=num[i]; i--; } num[i+1]=key; }} |
3 性能分析：
3.1 空間復(fù)雜度：如上代碼，使用了一個(gè)輔助單元key，空間復(fù)雜度為O(1)
3.2 時(shí)間復(fù)雜度：
3.2.1 最好情況：待排序記錄已經(jīng)是有序的，則一趟排序，關(guān)鍵字比較1次，記錄移動(dòng)2次。則整個(gè)過程
比較次數(shù)為
記錄移動(dòng)次數(shù)為
時(shí)間復(fù)雜度O(n)
3.2.2 最壞情況：待排序記錄已經(jīng)是逆序的，則一趟排序，關(guān)鍵字比較次數(shù)i次（從i-1到0），記錄移動(dòng)（i+2）次。整個(gè)過程
比較次數(shù)為
記錄移動(dòng)次數(shù)為
時(shí)間復(fù)雜度O(n^2)
3.2.3 平均時(shí)間復(fù)雜度：O(n^2)
3.3 穩(wěn)定性：穩(wěn)定
折半插入排序
1 排序思想：
直接排序的基礎(chǔ)上，將待排序的記錄Ri插入到已經(jīng)排好序的記錄R1，R2，……，R（N-1）中，由于記錄R1，R2，……，R（N-1）已經(jīng)排好序，所以在查找插入位置時(shí)可采用“折半查找”。
2 算法實(shí)現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// 折半插入排序void binary_insert_sort(int num[], int len){ int i,j,key,low,high,mid; for(i=1;i<len;i++){ key=num[i]; low=0; high=i-1; mid=(low+high)/2; // 尋找插入點(diǎn)，最終插入點(diǎn)在low while(low<=high){ if(key<num[mid]) high=mid-1; else low=mid+1; mid=(low+high)/2; } // 移動(dòng)記錄 for(j=i;j>low;j--){ num[j]=num[j-1]; } // 插入記錄 num[low]=key; }} |
3 性能分析：
3.1 空間復(fù)雜度：如上代碼，使用了一個(gè)輔助單元key，空間復(fù)雜度為O(1)
3.2 時(shí)間復(fù)雜度：雖然折半查找減少了記錄比較次數(shù)，但沒有減少移動(dòng)次數(shù)，因此時(shí)間復(fù)雜度同直接查找算法。
3.2.1 最好情況：時(shí)間復(fù)雜度O(n)
3.2.2 最壞情況：時(shí)間復(fù)雜度O(n^2)
3.2.3 平均時(shí)間復(fù)雜度：O(n^2)
3.3 穩(wěn)定性：穩(wěn)定
