插入排序(Insertion Sort)

插入排序是一種簡單直觀的排序算法。它的工作原理非常類似於我們抓撲克牌

對於未排序數據(右手抓到的牌)，在已排序序列(左手已經排好序的手牌)中從後向前掃描，找到相應位置並插入。

插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

具體算法描述如下：

從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下一位置
重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重複步驟2~5

插入排序的代碼如下：

#include

// 分類 ------------- 內部比較排序

// 數據結構 ---------- 數組

// 最差時間複雜度 ---- 最壞情況為輸入序列是降序排列的,此時時間複雜度O(n^2)

// 最優時間複雜度 ---- 最好情況為輸入序列是升序排列的,此時時間複雜度O(n)

// 平均時間複雜度 ---- O(n^2)

// 所需輔助空間 ------ O(1)

// 穩定性 ------------ 穩定

void InsertionSort(int A[], int n)

{

for (int i = 1; i < n; i++) // 類似抓撲克牌排序

{

int get = A[i]; // 右手抓到一張撲克牌

int

j = i - 1; // 拿在左手上的牌總是排序好的

while (j >= 0 && A[j] > get) // 將抓到的牌與手牌從右向左進行比較

{

A[j + 1] = A[j]; // 如果該手牌比抓到的牌大，就將其右移

j--;

}

A[j + 1] = get; // 直到該手牌比抓到的牌小(或二者相等)，將抓到的牌插入到該手牌右邊(相等元素的相對次序未變，所以插入排序是穩定的)

}

int main()

{

int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 從小到大插入排序

int n = sizeof(A) / sizeof(int);

InsertionSort(A, n);

printf("插入排序結果：");

for (int i = 0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return 0;

}

上述代碼對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行插入排序的實現過程如下

使用插入排序為一列數字進行排序的宏觀過程：

插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，比如量級小於千，那麼插入排序還是一個不錯的選擇。插入排序在工業級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用於少量元素的排序（通常為8個或以下）。

插入排序的改進：二分插入排序

對於插入排序，如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的次數，我們稱為二分插入排序，代碼如下：

#include

// 分類 -------------- 內部比較排序

// 數據結構 ---------- 數組

// 最差時間複雜度 ---- O(n^2)

// 最優時間複雜度 ---- O(nlogn)

// 平均時間複雜度 ---- O(n^2)

// 所需輔助空間 ------ O(1)

// 穩定性 ------------ 穩定

void InsertionSortDichotomy(int A[], int n)

{

for (int i = 1; i < n; i++)

{

int get = A[i]; // 右手抓到一張撲克牌

int left = 0; // 拿在左手上的牌總是排序好的，所以可以用二分法

int right = i - 1; // 手牌左右邊界進行初始化

while (left <= right) // 採用二分法定位新牌的位置

{

int mid = (left + right) / 2;

if (A[mid] > get)

right = mid - 1;

else

left = mid + 1;

}

for (int j = i - 1; j >= left; j--) // 將欲插入新牌位置右邊的牌整體向右移動一個單位

{

A[j + 1] = A[j];

}

A[left] = get; // 將抓到的牌插入手牌

}

int main()

{

int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 從小到大二分插入排序

int n = sizeof(A) / sizeof(int);

InsertionSortDichotomy(A, n);

printf("二分插入排序結果：");

for (int i = 0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return 0;

}

當n較大時，二分插入排序的比較次數比直接插入排序的最差情況好得多，但比直接插入排序的最好情況要差，所當以元素初始序列已經接近升序時，直接插入排序比二分插入排序比較次數少。二分插入排序元素移動次數與直接插入排序相同，依賴於元素初始序列。

插入排序的更高效改進：希爾排序(Shell Sort)

希爾排序，也叫遞減增量排序，是插入排序的一種更高效的改進版本。希爾排序是不穩定的排序算法。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序，算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。

假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用複雜度為O(n^2)的排序（冒泡排序或直接插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。

希爾排序的代碼如下：

#include

// 分類 -------------- 內部比較排序

// 數據結構 ---------- 數組

// 最差時間複雜度 ---- 根據步長序列的不同而不同。已知最好的為O(n(logn)^2)

// 最優時間複雜度 ---- O(n)

// 平均時間複雜度 ---- 根據步長序列的不同而不同。

// 所需輔助空間 ------ O(1)

// 穩定性 ------------ 不穩定

void ShellSort(int A[], int n)

{

int h = 0;

while (h <= n) // 生成初始增量

{

h = 3 * h + 1;

}

while (h >= 1)

{

for (int i = h; i < n; i++)

{

int j = i - h;

int get = A[i];

while (j >= 0 && A[j] > get)

{

A[j + h] = A[j];

j = j - h;

}

A[j + h] = get;

}

h = (h - 1) / 3; // 遞減增量

}

int main()

{

int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 從小到大希爾排序

int n = sizeof(A) / sizeof(int);

ShellSort(A, n);

printf("希爾排序結果：");

for (int i = 0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return 0;

}

以23, 10, 4, 1的步長序列進行希爾排序：

希爾排序是不穩定的排序算法，雖然一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂。

比如序列：{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 }，h=2時分成兩個子序列 { 3, 10, 7, 8, 20 } 和 { 5, 8, 2, 1, 6 } ，未排序之前第二個子序列中的8在前面，現在對兩個子序列進行插入排序，得到 { 3, 7, 8, 10, 20 } 和 { 1, 2, 5, 6, 8 } ，即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 } ，兩個8的相對次序發生了改變。