目錄

一、插入排序

二、直接插入排序（straight insertion sort）

1. 思路介紹

2. 代碼實現

3. 特性總結?

三、希爾排序（Shell sort）

1. 思路介紹

2. 代碼實現

3. 特性總結?

四、總結

---

一、插入排序

常見的排序算法有：

而本篇文章要介紹的是插入排序。

插入排序可以分為?直接插入排序?和?希爾排序?。

---

二、直接插入排序（straight insertion sort）

1. 思路介紹

????????直接插入排序是一種簡單的插入排序法，其基本思想是：

????????把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

如圖是基本思想的示意圖：排序思路：

1. 將整個數據劃分為有序區和無序區，初始時有序區只有一個數據，無序區包含了剩余所有待排序數據。
2. 將無序區的第一個數據插入到有序區的合適位置中，從而使無序區減少一個數據，有序區增加一個數據。
3. 重復步驟2，知道無序區沒有數據。

?對于一組數據：3，44，38，5，47，15，36，26，27，2，46，4，19，50，48? 它的排序個過程如下：

排序動圖如下：

排序一個數據的方法（排升序）：

????????將要排序數據先和有序區的最后一個數據比較，如果比該數據小，就將有序區該數據向后移動一位；如果比該數據大，就什么都不做，因為這樣已經將該要排序數據排好了。排序一個數據的代碼實現：

int end;// 有序區最后一個數據的下標
int tmp;// 該趟要排序的數據// 插入：將tmp插入到[0,end]區間中去
while (end >= 0)
{if (tmp < a[end]){a[end + 1] = a[end];// 后移有序區數據end--;}else{break;// 已經找到到合適位置，則退出循環}
}
a[end + 1] = tmp;// 插入合適位置

2. 代碼實現

排序一組數據，就只需要遍歷所有數據，逐步插入就可以了。則C語言代碼實現：

// 插入排序 - 排升序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;// 有序區最后一個數據的下標int tmp = a[i];// 該趟要排序的數據// 插入：將tmp插入到[0,end]區間中去while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];// 后移有序區數據end--;}else{break;// 已經找到到合適位置，則退出循環}}a[end + 1] = tmp;// 插入合適位置}
}

3. 特性總結?

直接插入排序的特性總結：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度：O(N^2)，最好情況：O(N)，最壞情況：O(N^2)
3. 空間復雜度：O(1)
4. 穩定性：穩定

---

三、希爾排序（Shell sort）

1. 思路介紹

????????希爾排序是對直接插入排序的一種改進。

????????希爾排序法又稱縮小增量法。希爾排序法的基本思想是：?

????????把待排序數據分割為若干子序列，再對各個子序列分別進行直接插入排序。

排序思路：

1. 先選定一個整數gap，表示間隔，把待排序文件中所有記錄分成gap個組，把所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行直接插入排序，讓整個數據接近有序。
2. 然后，每次將gap縮小一半，重復上述分組排序的工作，讓整個數據逐漸接近有序。
3. 當到達gap = 1時，就相當于普通的直接插入排序，但此時整個數據已經非常接近有序，排序效率是非常高。

所以，當gap>1時，這就是對數據的預排序；當gap=1時，這就是普通直接插入排序。

如圖是希爾排序的示意圖：

排序間隔為gap的一組。

如圖為假設 gap = 3 時其中一組數據的的直接插入排序：

排序間隔為gap的其中一組的代碼實現：

int gap;// 間隔
for (int i = gap; i < n; i += gap)
{int end = i - gap;// 有序區最后一個數據的下標int tmp = a[i];// 該趟要排序的數據// 間隔gap插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序區數據end -= gap;}else{break;// 已經找到到合適位置，則退出循環}}a[end + gap] = tmp;// 插入合適位置
}

那么排序gap時，所有組的實現就是通過調整狀態的起始位置，然后重復上述實現：

int gap;// 間隔
for (int j = 0; j < gap; j++)
{for (int i = j + gap; i < n; i += gap){int end = i - gap;// 有序區最后一個數據的下標int tmp = a[i];// 該趟要排序的數據// 間隔gap插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序區數據end -= gap;}else{break;// 已經找到到合適位置，則退出循環}}a[end + gap] = tmp;// 插入合適位置}
}

如圖所示，為當gap=3時的一組排序過程：

直到一組gap值的排序后，就可以再調整gap值為原來的一半，重復這個過程就可以了。

一般來說，gap的值是可以隨意取的。但

gap如果越大，那么間隔就大，排完一組的的時間就快，但這樣越不接近有序；

gap如果越小，那么間隔就小，排完一組的的時間就慢，但這樣越接近有序；

? ? ? ? 所以，希爾排序（Shell Sort）的間隔gap初始值通常取原數據長度的一半（即 gap = n/2），然后逐步縮小（如每次減半），最終縮小到1進行最后一次插入排序。

????????n/2 的間隔能確保子序列覆蓋整個數組，避免遺漏元素。

2. 代碼實現

希爾排序C語言實現如下：

//希爾排序
void ShellSort(int* a, int n)
{int gap = n;// 間隔while (gap > 1){gap /= 2;for (int j = 0; j < gap; j++){for (int i = j + gap; i < n; i += gap){int end = i - gap;// 有序區最后一個數據的下標int tmp = a[i];// 該趟要排序的數據// 插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序區數據end -= gap;}else{break;// 已經找到到合適位置，則退出循環}}a[end + gap] = tmp;// 插入合適位置}}}
}

可以發現這里的循環很多，所以這里可以簡化一下：

void ShellSort(int* a, int n)
{int gap = n;// 間隔while (gap > 1){gap /= 2;for (int i = gap; i < n; i++){int end = i - gap;// 有序區最后一個數據的下標int tmp = a[i];// 該趟要排序的數據// 插入while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];// 后移有序區數據end -= gap;}else{break;// 已經找到到合適位置，則退出循環}}a[end + gap] = tmp;// 插入合適位置}}
}

3. 特性總結?

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。
2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。
3. 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算。一般來說，時間復雜度是~之間。
4. 空間復雜度：O(1)
5. 穩定性：不穩定

---

四、總結

• 直接插入排序通過將待排序元素逐個插入已排序序列來實現排序，時間復雜度為O(N^2)，適用于接近有序的數據。
• 希爾排序是直接插入排序的改進版本，采用分組排序策略，先通過較大間隔進行預排序，再逐步縮小間隔直至1，提高了整體排序效率。
• 希爾排序的時間復雜度難以精確計算，但優于直接插入排序，空間復雜度均為O(1)。
• 兩種算法的主要區別在于：直接插入排序穩定但效率較低，希爾排序不穩定但效率較高。

感謝各位觀看！希望能多多支持！