排序算法

堆排序是通过堆这种特殊的数据结构进行排序的一种排序算法。

堆：由完全二叉树构成，且具有一定的大小关系；二叉树根为最小值的堆被称为小顶堆，反之，根节点为最大元素的堆被称为大顶堆。 对于一个堆，按层进行编号，根节点为0号，依次往下编号，对应于一个序列（集合）的下标。 堆的两个重要性质： 1、结点i的父节点为i/2； 2、结点i的左子节点为2i，右子节点为2i+1。

堆排序的基本思想是：设给待排序列构造成一个大顶堆（升序大顶堆、降序小顶堆），堆顶元素与最后一个元素交换，即把待排序列中的最大值放到最后一个位置。剩下的元素仍然构成一个堆，继续构造成为大顶堆，交换倒数第二个数······，直到堆只剩一个元素。

堆排序算法的时间复杂度为O(nlogn)。

伪代码出自《算法导论》原书第3版，机械工业出版社，Thomas H.Cormen Charles E.Leiserson著

若存在序列：{7, 50, 1, 4, 32, 7, 9, 5, 25, 6}，利用堆排序进行排序。 1、构造堆 2、构造出大顶堆 （方法一：时间复杂度nlogn） （方法二：时间复杂度n） （两种方法构造的大顶堆有所不同，但最终排序结果是一样的。接下去的步骤采用第一种方法。）

3、将堆顶的50与最后一个元素6交换，50已排好； 4、剩下的元素构造大顶堆。得到堆顶元素32，与最后一个元素4交换，32已排好； 5、重复第4步的操作，直至排序完成。

以上gif制作均来源于VisuAlgo https://