《大话数据结构》第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章最经典的两种高效排序归并排序和快速排序。

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

相关推荐

树莓派auto exposure中曝光路径设计思路解析

加载慢3秒，AI直接跳过你

会计专业大学期间考什么证

更多资讯

2026年会员管理系统多少钱？先算清交易费率和第二年续费这笔账

Agentic Coding：从生成代码到交付结果的AI编程范式

AI代码评审两件套：superpowers-skills中如何请求评审，以及如何优雅地回怼反馈

Milvus 索引不重建也能查：为什么召回率悄悄掉到随机水平

MySQL 8.0 联合索引走错：为什么加了索引查询反而从 200ms 变成 8s

【无套路自取】给 Inspector 换上 X 光镜：Odin V3.5 属性绘制器，让 Unity 数据编辑省心得多

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？