面试官常问哪种排序算法？——堆排序应用广泛吗？

本文共计1414个文字，预计阅读时间需要6分钟。

比较类排序系列 - 堆排序 + 1. 原理 + 堆排序是利用堆进行排序的方法。假设进行升序排序，其基本思想是将待排序序列构造成一个大顶堆，此时序列的最大值就是堆顶的元素。将其移除后，再调整剩余元素，使之重新满足大顶堆的性质，然后再次移除最大值，如此循环，直到序列全部排序。

比较类排序系列-堆排序

1. 原理

堆排序是利用堆进行排序的方法。假设进行升序排序，则它的基本思想是，将待排序的序列构造成一个大顶堆，这是一个建堆的过程。此时，整个序列的最大值就是堆顶的根结点。将它与堆数组的末尾元素交换，此时末尾元素就是最大值，然后将剩余的n-1个序列，从根开始进行向下调整，重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行交换，向下调整，便能得到一个有序序列了。如果是降序排序，则是用小顶堆，后面的过程类似。

如下图所示

1.1向下调整

堆的向下调整主要是为了让堆中的每一个数据都满足堆的性质。如果某个数据所在的位置不满足堆的性质，则需要对其进行向下调整，给数据找到一个合适的位置。向下调整的前提条件是，当前被调整数据的子结构必须已经是一个堆。向下调整的过程如下：

从左右孩子中选择一个最大的

如果当前被调整的数据小于第一步选出的孩子，则进行交换，更新需要调整的数据位置以及孩子的位置，继续执行第一步。否则结束调整。

当更新的位置超出序列的范围则结束调整。