堆排序

面试官：写一个堆排吧 我心想：幸好昨天刚看

堆排是基于堆的一种排序算法，对于堆的了解，请看可以管理时间的二叉堆（如果对堆的插入和删除不清楚，强烈建议先看堆），今天我们聊聊堆排的思想，复杂度以及稳定性

堆排思想

过了几天后，谦子高兴地跑到老师跟前

老师，你的那个方法太好了,现在做事非常有次序克

谦子心想：上次去溪边游玩不是已经出过这个题吗，当时学会了冒泡排序，这次肯定不是那么简单，肯定和前几天的堆有关系

这个应该用到堆

谦子画了一个图解释道

初始的时候，无序数组逻辑上可以看成一颗完全二叉树

每个叶子节点可以视为一个大小为一的堆，我们可以自底向上从非叶子节点开始每层从右至左给每个节点都调用下沉(sink)方法，这样以当前节点为根节点的树就变为堆了

然后给左边的节点4执行下沉(sink)操作（同一层从右向左）

最后根节点执行下沉(sink)操作

又要写代码，谦子心想，虽说心中这样想，但还是要写的，思考了一会，只见谦子写下了如下代码

这里的 heapSize/2 就是第一个非叶子节点的下标

过了一会谦子又写出了删除最小值的代码

恩恩，不错，那顺便写一下排序的代码吧

前两个都写出来了，剩下的排序就很简单了，按照之前的思路，先建立一个小根堆，然后不断地删除堆顶最小元素，删除N-1次就OK了

只需删除N-1次，剩下的那个自然是最大的，所以我循环N-1次

恩恩，很好，这个排序就是今天要给你说的另一个排序：堆排序

谦子暗自惊叹老师的功力，不知不觉又学到了一个排序方法

时间复杂度

那你分析一下这个堆排序的时间复杂度吧

看到数学头疼的可以直接跳过看结论

谦子还没缓过神，又来了一个最让他头疼的时间复杂度

这个。。。，弟子不才，还请老师指点

这个排序时间复杂度稍微有点难，但只要你静下心来一步一步算，其实也不难

克拿出了笔和纸

你想一下堆排的整个过程，第一步建堆，第二步执行N-1次deleteMin()方法,最后取两者复杂度较高的就行了

建堆时间复杂度

建堆的时候时间消耗在下沉操作上，而下沉操作最多下沉到底，显然，高度为h的节点下沉代价为O(h)

堆中所有元素下沉代价之和就是建堆的代价（时间复杂度）

叶子节点高度为0，下沉代价为0

把堆中不同高度中的所有节点相加起来就是全部的节点

所以问题变为：

① 高度最高多高（高度上界）

② 高度h有多少节点

这里你记住两个结论

这里我们把不同高度的每个节点执行sink所需要的代价累加起来

感觉复杂，你最终记住建堆复杂度为O(n)就行了

N-1次删除复杂度

接下来就是N-1次的删除了

n-1次调用deleteMin

deleteMin中包含 swap操作和 sink操作

swap操作代价为常数，sink操作代价为lgn,swap操作相对于sink操作可以忽略不计

则相当于进行了n-1次sink操作

则一共花费的代价为：(n-1)*lgn ~ nlgn

故时间复杂度为O(nlgn)

两个步骤相加的复杂度为：O(n)+O(nlgn)，O(nlgn)复杂度高于O(n)，所以堆排序的时间复杂度为O(nlgn)

哦，这样啊，懂了

那你说说堆排序是不是稳定的

不是稳定的，就拿5,7,13,5，这个序列来说吧，我用大根堆的结构排序,排序前后两个5的位置会发生变化

谦子说着说着画了一个图

初始状态的5的先后顺序和排完序的顺序明显不一样了（黄色5跑到红色5左边去了），所以这个排序不是稳定的