967
排序算法係列之插入排序
算法排序之插入排序
基本思想
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
- 從第一個元素開始，該元素可以認為已經被排序
- 取出下一個元素，在已經排序的元素序列中從後向前掃描
- 如果該元素（已排序）大於新元素，將該元素移到下一位置
- 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
- 將新元素插入到該位置後
- 重複步驟2~5
偽碼描述：
INSERTION-SORT(A)
1 for j = 2 to length[A]
2 do key = A[j]
3 i = j-1
4 while i > 0 and A[i] > key
5 do A[i+1] = A[i]
6 i = i-1
7 A[i+1] = key
動態演示
使用插入排序為一列數字進行排序的過程
時間複雜度分析
如果目標是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數減去(n-1)次。平均來說插入排序算法複雜度為O(n2)。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。 插入排序在工業級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用於少量元素的排序（通常為8個或以下）。
算法改進
一.如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序
PS:雖然試用了二分查找插入位置，時間為O（nlgn），但是插入時移位仍為O（n*n），所以整體還是沒有改變時間複雜度。
偽碼描述：
INSERTION-SORT(A)
1 for j = 2 to length[A]
2 do key = A[j]
3 high = j-1
4 low = 1
5 while low < high
6 mid = (low + high)/2
7 if key = A[mid] then
8 break
9 if key < A[mid] then
10 high = mid - 1
11 if key > A[mid] then
12 low = mid + 1
13 for i = mid to j-1
14 A[i+1] = A[i]
15 A[mid] = key
二.查找比較操作和記錄移動操作交替地進行的方法
具體做法：
將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：
① 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置；
②若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。
關鍵字比R[i]的關鍵字大的記錄均已後移，所以j+1的位置已經騰空，隻要將R[i]直接插入此位置即可完成一趟直接插入排序。
算法C實現
void insertion_sort(char array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;
//與已排序的數逐一比較，大於temp時，該數向後移
while((j>=first) && (array[j] > temp)) //當first=0，j循環到-1時，由於[[短路求值]]，不會運算array[-1]
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp; //被排序數放到正確的位置
}
}最後更新：2017-04-03 19:13:18