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