《大话数据结构》第9章精读：希尔排序与堆排序完整 C++ 实现

1. 引言从简单排序到高效排序简单排序冒泡、直接插入、简单选择的平均时间复杂度都是 O(n²)当数据量增大时效率明显不足。《大话数据结构》第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(n²)空间复杂度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章最经典的两种高效排序归并排序和快速排序。