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