一、算法思想
希爾排序（Shell Sort），也被叫做縮小增量排序，是插入排序的一種改進版本。希爾排序的核心在于先將整個待排序的記錄序列分割成若干個子序列，分別進行直接插入排序。隨著增量逐漸減小，子序列的長度慢慢增加，整個序列會變得越來越接近有序。當增量減至 1 時，整個序列就會被合并為一個，再進行一次直接插入排序，最終完成整個排序過程。
與插入排序對比
插入排序在處理部分有序的數組時效率更高，而希爾排序正是利用了這一特性。它通過分組預排序，讓數組先達到部分有序的狀態，最后再進行一次插入排序，從而減少了元素移動的次數。
算法步驟
- 選擇增量序列：確定一個遞減的增量序列，常用的增量序列有希爾增量（n/2, n/4, ..., 1）、Knuth 增量（3k +1）等。
- 按增量分組：根據當前增量將數組分成若干個子序列，每個子序列的元素間隔為當前增量。
- 對子序列排序：對每個子序列分別進行插入排序。
- 減小增量：增量逐漸減小，重復步驟 2 和 3，直到增量為 1。
- 最終排序：當增量為 1 時，整個數組作為一個子序列進行一次插入排序，此時數組已基本有序，插入排序效率較高。
二、手動排序示例
下面以數組?[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]?為例，詳細展示希爾排序的過程。這里我們采用希爾增量序列（初始增量為數組長度的一半，之后每次減半）。
初始數組
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
第一趟排序（增量為 5）
將數組分成 5 個子序列：
- 子序列 1：[8, 3] → 排序后 [3, 8]
- 子序列 2：[9, 5] → 排序后 [5, 9]
- 子序列 3：[1, 4] → 排序后 [1, 4]
- 子序列 4：[7, 6] → 排序后 [6, 7]
- 子序列 5：[2, 0] → 排序后 [0, 2]
排序后的數組：
[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第二趟排序（增量為 2）
將數組分成 2 個子序列：
- 子序列 1：[3, 1, 0, 9, 7] → 排序后 [0, 1, 3, 7, 9]
- 子序列 2：[5, 6, 8, 4, 2] → 排序后 [2, 4, 5, 6, 8]
排序后的數組：
[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第三趟排序（增量為 1）
此時進行直接插入排序：
[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最終得到有序數組：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
三、C 語言實現代碼
下面是希爾排序的 C 語言實現，采用希爾增量序列：
#include <stdio.h>// 希爾排序函數
void shellSort(int arr[], int n) {// 初始增量為數組長度的一半，之后每次減半，直到增量為1for (int gap = n / 2; gap > 0; gap /= 2) {// 對每個子序列進行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 插入排序邏輯：將當前元素插入到其所在子序列的正確位置for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}// 打印數組函數
void printArray(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函數
int main() {int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};int n = sizeof(arr) / sizeof(arr[0]);printf("原始數組: \n");printArray(arr, n);shellSort(arr, n);printf("排序后的數組: \n");printArray(arr, n);return 0;
}
四、代碼解釋
希爾排序函數?shellSort
增量序列控制：
- 初始增量?
gap?設為數組長度的一半（n/2）。 - 每輪循環后將增量減半（
gap /= 2），直到增量為 1。
- 初始增量?
分組插入排序：
- 對于每個增量?
gap，將數組分為?gap?個子序列。 - 對每個子序列進行插入排序，確保元素在各自子序列中有序。
- 對于每個增量?
插入排序優化：
- 使用臨時變量?
temp?保存當前元素。 - 通過比較和移動元素，找到?
temp?應插入的位置。
- 使用臨時變量?
主函數?main
- 數組初始化：定義待排序的數組?
arr。 - 排序前輸出：調用?
printArray?函數顯示原始數組。 - 調用排序：調用?
shellSort?函數對數組進行排序。 - 排序后輸出：再次調用?
printArray?函數顯示排序后的數組。
五、算法復雜度與穩定性
時間復雜度
希爾排序的時間復雜度與增量序列的選擇有關，不同的增量序列會導致不同的時間復雜度：
- 最壞情況：希爾增量序列下為 O (n2)
- 平均情況：取決于增量序列，可能達到 O (n^1.3) 或更好
- 最好情況：當數組已經有序時為 O (n)
空間復雜度
希爾排序只需要常數級的額外空間，因此空間復雜度為 O (1)。
穩定性
希爾排序是一種不穩定的排序算法，因為在不同的子序列插入排序過程中，相同元素的相對順序可能會發生改變。
六、希爾排序的優缺點
優點
- 高效性：對于中等規模的數據，希爾排序的性能通常優于直接插入排序和選擇排序。
- 空間效率：只需要常數級的額外空間。
- 實現簡單：代碼結構相對簡單，易于理解和實現。
缺點
- 復雜度分析困難：時間復雜度依賴于增量序列的選擇，難以精確分析。
- 不穩定性：不適合需要保持元素相對順序的應用場景。
七、適用場景
希爾排序適用于以下場景：
- 數據量中等且不需要穩定性的排序任務。
- 對內存使用有限制的環境，因為它只需要 O (1) 的額外空間。
- 作為更復雜排序算法的預處理步驟。
希爾排序通過巧妙的分組策略，打破了傳統插入排序的性能瓶頸，為排序算法的發展開辟了新的思路。在實際應用中，合理選擇增量序列可以顯著提高希爾排序的性能。
