算法和数据结构2.4堆排序

堆排序利用了数据结构中的堆。关于堆的简单介绍

对如下数据进行排序

 5  2  7  3  6  1  4

首先在堆中存储所有数据，并按照降序来建堆。（升序也可以）

1.png

现在将堆顶数据7取出，放在排序的末位

2.png

得到的结果是

3.png

[,,,,,,7]

调整堆：
调整堆的方法

将堆顶数据6取出,放在排序的末位：

4.png

得到的结果如下：

[,,,,,6,7]

继续调整堆：

将堆顶元素5取出，放在排序末位

5.png

[,,,,5,6,7]

继续调整堆，
排序中...
直到堆中元素被取出完成之后。排序步骤完成。

时间计算：

堆排序一开始需要将n个数据存进堆里面，所需要的时间为O（nlogn）

排序过程中，堆从空堆的状态开始，逐渐被数据填满。
由于堆的高度小于log₂n,所以插入一个数据所需要的时间为O(logn).每轮取出最大的数据并重构所需要的时间为O（logn）

由于总有n轮，所以重构后排序时间也是O(nlogn)

因此，整体来看堆排序的时间复杂度为O(nlogn).

这样看来，堆排序的运行时间比冒泡排序，选择排序，插入排序的时间O(n²)都要短。

但是不方便的是，要实现堆这个复杂的数据结构，代码实现起来比较困难。

其他：

一般来说，需要排序的数据都存储在数组中。这次我们使用了堆这种数据结构，但实际上，这也相当于将堆嵌入到包含了序列的数组中，然后在数组中通过交换数据来进行排序。

具体来说就是让堆中的各结点和数组像下图这样的对应关系。这样约等于强行在数组中使用了堆结构来秀操作。

7.png