堆排序
2021-02-17 18:17
标签：-- class 方法 nlogn 替换 递归 flag 时间 稳定性 分为大顶堆和小顶堆，是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以用到上一次的排序结果，所以不像其他一般的排序方法一样，每次都要进行n-1次的比较，复杂度为O(nlogn)。 将堆的内容填入一个一维数组，这样通过下标就能计算出每个结点的父子节点，编号顺序从0开始，从左往右，从上至下层次遍历。a[10] = {2,8,5,10,9,12,7,14,15,13} 若一个结点的下标为k，那么它的父结点为(k-1)/2，其子节点为2k+1和2k+2 例：数字为10的节点的下标为3，父结点为1号：8，子节点为7号和8号：14，15 1）利用给定数组创建一个堆H[0..n-1]，输出堆顶元素 2）以最后一个元素代替堆顶，调整成堆，输出堆顶元素 3）把堆的尺寸缩小1 4） 重复步骤2，直到堆的尺寸为1 先构造一个大顶堆，移除最大元素（根节点），将最大元素与最小元素替换，重新构造一个大顶堆，循环移除 实现代码 最差时间复杂度O(n log n) 稳定性：不稳定 注意：此排序方法不适用于个数少的序列，因为初始构建堆需要时间 堆排序 标签：-- class 方法 nlogn 替换 递归 flag 时间 稳定性 原文地址：https://www.cnblogs.com/jpzhu/p/12696863.html概念
完全二叉树的性质
流程
1 void HeapBuild(vectorint> &nums, int root, int length)
2 {
3 int lchild = root * 2 + 1;
4 if (lchild //左子结点下标不能超出数组的长度
5 {
6 int flag = lchild;//flag保存左右节点中最大值的下标
7 int rchild = lchild + 1;
8 if (rchild nums[flag])
9 flag = rchild;//找出左右子结点中的最大值
10
11 if (nums[root] nums[flag])
12 {
13 swap(nums[root], nums[flag]);
14 HeapBuild(nums, flag, length);//从此次最大子节点的那个位置开始递归建堆
15 }
16 }
17 }
18
19 void HeapSort(vectorint> &nums)
20 {
21 int len = nums.size();
22 for (int i = len / 2; i >= 0; i--)//从最后一个非叶子节点的父节点开始建堆
23 {
24 HeapBuild(nums, i, len);
25 }
26
27 for (int j = len - 1; j > 0; j--)
28 {
29 swap(nums[0], nums[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
30 HeapBuild(nums, 0, j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
31 }
32 }
性能
最优时间复杂度O(n log n)
平均时间复杂度O(n log n)
最差空间复杂度O(n)
上一篇：直接插入排序
下一篇：Python 练习实例62