《我的第一本算法书》阅读笔记 2-5 堆排序

超、凢脫俗 2022-10-22 05:24 135阅读 0赞

堆排序的特点是利用了数据结构中的堆。关于堆的详细说明在 1-7 节。[《我的第一本算法书》阅读笔记 1-7 堆][1-7]

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

首先，在堆中存储所有的数据，并按降序来构建堆。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

现在，所有数据都存进堆里了。为了排序，需要再从堆中把数据一个个取出来。

--------------------

从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

我们来试一试吧。首先取出根结点的数字7。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

重新构造堆。重构的规则请参考 1-7节的内容。

--------------------

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

同样地，取出根结点的数字6，将它放在右数第2个位置上。

![20210404143402610.png][]

重新构造堆。

--------------------

![20210404143429330.png][]

重复上述操作直到堆变空为止.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

从堆中取出了所有数字，排序完成。

### 解说 ###

堆排序一开始需要将 n 个数据存进堆里，所需时间为 O(nlogn)。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于 ![\\log\_2n][log_2n]，所以插入 1 个数据所需要 的时间为 O(logn)。

每轮取出最大的数据并重构堆所需要的时间为 O(logn)。由于总共有 n 轮，所以重 构后排序的时间也是 O(nlogn)。因此，整体来看堆排序的**时间复杂度为 O(nlogn)**。

这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间 O(n2 ) 都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

“**空间复杂度**”指占内存大小，堆排序每次只对一个元素操作，是就地排序，所用**辅助空间O(1)**

### 补充说明 ###

一般来说，需要排序的数据都存储在数组中。这次我们使用了堆这种数据结构，但实际上，这也相当于将堆嵌入到包含了序列的数组中，然后在数组中通过交换数据来进行排序。具体来说，就是让堆中的各结点和数组像下图这样呈对应关系。正如大家所见， 这可以说是强行在数组中使用了堆结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[1-7]: https://blog.csdn.net/Drifter_Galaxy/article/details/115420430?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/c5223c89e15c401198e96b46e6f2a49b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/eb65257f5b7e4ee1b4639729106b94cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/acdc748160e34fcaae19f38fe7cdf165.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/fe805202fe6041b3923fefa162241dc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/1818ddc6b9a34538ae914ce5c9dc1b96.png
[20210404143402610.png]: /images/20221022/7df477d6ec26459e8f6a184e9be34bd6.png
[20210404143429330.png]: /images/20221022/ce666b36b96c4795bc6ae8974bce653b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/c694b1cfdbe64bdca08b3799fa243b8d.png
[log_2n]: https://latex.codecogs.com/gif.latex?%5Clog_2n
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/c2a99302e27a441e8ab7a64cc2a16dc8.png