堆排序
mmexport1520334289708.gif
阅读原文
堆排是基于堆的一种排序算法，对于堆的了解，请看什么是堆排序（如果对堆的插入和删除不清楚，强烈建议先看堆），今天我们聊聊堆排的思想，复杂度以及稳定性。
堆排思想
前情回顾：克给谦子解决了时间管理上的问题：什么是堆排序
过了几天后，谦子高兴地跑到老师跟前
1.png
早知不来了，谦子心想
2.png
谦子心想：上次去溪边游玩不是已经出过这个题吗，当时学会了冒泡排序，这次肯定不是那么简单，肯定和前几天的堆有关系
3.png
删除中交换操作会破坏堆有序
但下沉操作会重新调整堆
谦子画了一个图解释道
4.png
5.png
删除包括三个步骤：
① 交换堆顶与堆最后一个元素
② 堆大小(heapSize)减一
③ 调整堆(sink(arr,1))
具体讲解请看:二叉堆
6.png
建堆
7.png
上浮(swim)操作会保持堆有序
8.png
9.png
10.png
11.png
12.png
13.png
14.png
注意：在下沉(sink)某个节点的时候，这个节点的两个孩子必须是堆
堆排代码
15.png
克突然话锋一转
16.png
又要写代码，谦子心想，虽说心中这样想，但还是要写的，思考了一会，只见谦子写下了如下代码
/**
* 将传进来的无序数组变成小根堆
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
public void buildHeap(int[] arr) {
// 从第一个非叶子节点开始sink调整，也就是堆大小的一半处
for(int i = heapSize/2; i >= 1; i --) {
sink(arr, i); // 调整以节点i为父节点的树为堆（符合堆有序）
}
}
17.png
谦子解释道
18.png
过了一会谦子又写出了删除最小值的代码
/**
* 删除堆中最小的元素（通过heapSize--逻辑上删除）
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
private void deleteMin(int[] arr) {
// 交换堆顶和堆最后一个元素
swap(arr, index1, heapSize);
heapSize --;
sink(arr, parentIndex:1); // 调整使之重新变成堆有序
}
19.png
前两个都写出来了，剩下的排序就很简单了，按照之前的思路，先建立一个小根堆，然后不断地删除堆顶最小元素，删除N-1次就OK了
/**
* 对给定数组arr排序，使之为降序
* @param arr a[1...n]为有效元素，a[0]为无效元素
*/
public void heapSize(int[] arr) {
int N = arr.length-1;
buildHeap(arr); // 建小根堆
// n个元素的小根堆，排序（删除堆顶）n-1次，数组就变成降序了
for(int i = 1; i <= n-1; i ++) {
deleteMin(arr); // 删除arr数组中最小的值
}
}
20.png
谦子解释道
21.png
谦子暗自惊叹老师的功力，不知不觉又学到了一个排序方法
时间复杂度
22.png
看到数学头疼的可以直接跳过看结论
谦子还没缓过神，又来了一个最让他头疼的时间复杂度
23.png
克拿出了笔和纸
24.png
建堆时间复杂度
25.png
叶子节点高度为0，下沉代价为0
谦子目不转睛地
26.png
所以问题变为：
① 高度最高多高（高度上界）
② 高度h有多少节点
这里你记住两个结论
29.png
30.png
31.png
32.png
谦子长舒一口气
n-1次删除 复杂度
33.png
n-1次调用deleteMin
deleteMin中包含 swap操作和 sink操作
swap操作代价为常数，sink操作代价为lgn,swap操作相对于sink操作可以忽略不计
则相当于进行了n-1次sink操作
则一共花费的代价为：(n-1)*lgn ~ nlgn
故时间复杂度为O(nlgn)
34.png
稳定性
35.png
谦子说着说着画了一个图
36.png
37.png
摘录自：趣谈编程
