1. 引言從簡單排序到高效排序簡單排序冒泡、直接插入、簡單選擇的平均時間復雜度都是 O(n2)當數據量增大時效率明顯不足。《大話數據結構》第9章接下來介紹了兩種重要的改進算法希爾排序插入排序的改進和堆排序選擇排序的改進。本文基于《大話數據結構》第9章內容結合《C Primer Plus》的編程視角給出兩種算法的完整 C 實現、復雜度分析、對比表格與測試代碼方便直接復制運行。2. 希爾排序Shell Sort2.1 核心思想把數組按一定增量gap分組對每組進行直接插入排序。隨著增量逐漸減小數組越來越接近有序最后一趟增量變為 1 時就是普通的插入排序。希爾排序通過“跳躍式”的比較與移動大幅減少了插入排序中元素的移動次數。下圖展示了希爾排序的分組與跳躍式移動過程2.2 完整實現常用 Knuth 序列#include iostream #include vector using namespace std; void ShellSort(vectorint arr) { int n arr.size(); // 使用 Knuth 序列gap gap * 3 1 int gap 1; while (gap n / 3) { gap gap * 3 1; } while (gap 1) { // 對每個分組進行插入排序 for (int i gap; i n; i) { int key arr[i]; int j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } gap / 3; // 縮小增量 } }2.3 復雜度與特點指標說明平均時間復雜度約 O(n^1.3) O(n^1.5)取決于增量序列最壞時間復雜度O(n2)空間復雜度O(1)穩定性不穩定優點實現簡單對中等規模數據表現較好代碼開銷小。3. 堆排序Heap Sort3.1 核心思想利用堆這種數據結構。先把數組建成大頂堆此時堆頂是最大值把它與末尾元素交換然后把剩余部分重新調整為堆重復此過程。堆排序是選擇排序的高效改進時間復雜度穩定在 O(n log n)。下圖展示了大頂堆的建堆與交換過程3.2 完整實現// 調整以 index 為根的子樹使其符合大頂堆 void heapify(vectorint arr, int n, int index) { int largest index; // 假設當前節點最大 int left 2 * index 1; // 左孩子 int right 2 * index 2; // 右孩子 if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } // 如果最大值不是當前節點就交換并繼續向下調整 if (largest ! index) { swap(arr[index], arr[largest]); heapify(arr, n, largest); } } void HeapSort(vectorint arr) { int n arr.size(); // 1. 建堆從最后一個非葉子節點開始向前調整 for (int i n / 2 - 1; i 0; --i) { heapify(arr, n, i); } // 2. 排序每次把堆頂最大值換到末尾再調整剩余部分 for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); // 堆頂與末尾交換 heapify(arr, i, 0); // 調整剩余元素 } }3.3 復雜度與特點指標說明時間復雜度最好、平均、最壞都是 O(n log n)空間復雜度O(1)原地排序穩定性不穩定特點建堆時間是 O(n)非常高效。適合大數據量且不需要額外內存。4. 兩種算法對比對比維度希爾排序堆排序時間復雜度約 O(n^1.3)O(n log n) 穩定空間復雜度O(1)O(1)穩定性不穩定不穩定實現難度較低中等需要理解堆調整適用場景中等數據量、代碼簡單要求大數據量、要求時間穩定是否原地排序是是5. 完整測試代碼#include iostream #include vector using namespace std; void printArray(const vectorint arr) { for (int x : arr) cout x ; cout endl; } int main() { vectorint arr1 {49, 38, 65, 97, 76, 13, 27, 49, 55, 4}; vectorint arr2 arr1; cout 原數組; printArray(arr1); ShellSort(arr1); cout 希爾排序后; printArray(arr1); HeapSort(arr2); cout 堆排序后; printArray(arr2); return 0; }運行結果原數組49 38 65 97 76 13 27 49 55 4 希爾排序后4 13 27 38 49 49 55 65 76 97 堆排序后4 13 27 38 49 49 55 65 76 976. 總結與思考希爾排序通過增量分組打破了插入排序只能移動相鄰元素的限制顯著提升了效率。堆排序把“每次選最值”的思想用堆結構高效實現時間復雜度穩定在 O(n log n)。結合《C Primer Plus》的思考堆排序中的 heapify 是典型的遞歸思想對應書中對遞歸與樹形結構的講解。兩種算法都做到了原地排序體現了“空間效率優先”的設計。下一篇將講解第9章最經典的兩種高效排序歸并排序和快速排序。