堆排序 | Jimmy Huang’s Blog²

type

status

一、什么是堆排序

堆排序是利用堆这种数据结构而设计堆一种排序算法，堆排序是一种选择排序。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质。

二、先修知识

1、什么是二叉树

2、什么是完全二叉树

设一个高度为 h、有 n 个结点的二叉树，当且仅当其每个结点都与高度为 h 的满二又树中编号 1~n 的结点对应时，称为完全二叉树。

3、什么是堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

三、动图演示

动图来自菜鸟教程

建议看这个https://www.cnblogs.com/chengxiao/p/6129630.html(这篇写的真好)

四、实现方式

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

一般升序大顶堆，降序小顶堆

将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

简单理解：就是因为堆的特性

堆内最大值是在最上面堆，也就是数组第一个数，最小值是数组最后一个数

所以我们每次把最小值和最大值换一个位置，然后对从0到最后一个数(最大值)前一个数范围内进行向下调整。以此反复，就可以依次把堆内的最大值放到数组最后，从后往前排。

五、关于堆排序的性能参数

1、时间复杂度

2、空间复杂度

3、是否稳定

不稳定

4、适用于何类型存储

顺序存储与链式存储

六、代码实现

1、算法

2、实例实现

七、遇到的问题

实现的方式是用的《算法笔记》p339中的堆排序算法，但是不知道为什么，我觉得他好像写的有点问题，例如在heapSort中，downAdjust(0,i-1)是从堆顶到堆末，除了刚刚交换过去的最大值（在i位置）进行调整，但是《算法笔记》中给出的是downAdjust(1,i-1)进行调整的。

因此我刚开始用其中给出的代码并不能实现排序，debug后才发现原因。

我仔细审查了他的实现方法，都是默认heap[1]为堆顶元素。

这是为啥呢？费解，是因为哨兵吗？有空再看看