点击关注公众号，干货第一时间送达
上篇文章：数据结构和算法【37】归并排序
小编演示了归并排序。
今天再来看看，堆排序。
一、屏幕前的吴彦祖和刘亦菲们，请看
堆排序，利用的是把无序数组，映射成二叉树，
利用二叉树的大根堆或者小根堆性质，完成排序的一种方法。
举个例子：（该例子是要按照从小到大的顺序排序，所以利用大根堆。如果是倒序，利用小根堆即可）
1，把数组 arr = {8,6,1,2,7,9,11,0} 映射成二叉树
2，把上面的二叉树，构建成大根堆（大根堆可以理解为，二叉树的任意节点值大于左右孩子的最大值）
构建的步骤，可以从二叉树根节点开始，
依次判断每个节点，和其父节点的关系，
如果当前节点值大于父节点值，则交换位置
此时节点8没有父节点，所以继续移动，
这个移动时按照 arr 数组的顺序遍历的。
依次是节点6，节点1。
当到达节点7时，发现节点7，大于父节点6，所以交换：
交换节点7和节点6后：
遍历继续，然后可以发现节点9，大于节点1，交换：
此时指针会回退到节点9，判断节点9的父节点，
发现节点9，大于父节点8，进行交换：
遍历继续，发现节点11，大于父节点8，交换：
指针回退到节点11，节点11仍然大于此时的父节点9，交换：
最后遍历到节点0，也就是数组 arr 的最后位置，
节点0不比父节点大，所以构建大根堆过程结束。
此时可以发现，二叉树中任意节点都大于左右子节点的最大值。
而数组arr，也转换成了 arr = {11, 7, 9, 2, 6, 1, 8, 0}
仍然是无序的。
下面需要进行大根堆的排序。
3，排序大根堆，就是把数组末尾值和头部值交换，再按照大根堆性质排序
因为通过步骤2的构建，大根堆的最上节点，肯定是最大值，
然后我们把这个最大值，换到数组末尾，也是二叉树的最下叶子节点：
相当于把数组arr 转换成 arr = {0, 7, 9, 2, 6, 1, 8, 11}
最后一位无需参加排序，因为肯定是最大值。
然后，从数组0位置开始遍历，按照步骤2的方式，调整堆
但是，不考虑最后的叶子节点：
再次进行排序后，还会发现二叉树的根节点肯定是倒数第二大的值，
然后放到数组倒数第二的位置即可。
通过这样，即可完成堆排序。
看看代码。
完整代码：
public class CodingDemo {
/**
* TODO: 堆排序
* @param arr
*/
private static void heapSort(int[] arr){
//1， 构建堆
for (int i = 0; i < arr.length - 1; i++) {
heapInsert(arr, i);
}
//2，依次把末尾的数和头部数进行交换，缩短遍历范围
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapif(arr, 0, i);
}
}
//构建大根堆
private static void heapInsert(int[] arr, int i){
int parent = 0;
while (i != 0){
parent = (i - 1) / 2;
if (arr[parent] < arr[i]){
swap(arr, parent, i);
} else {
break;
}
i = parent;
}
}
//交换
private static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//遍历堆，并且调整
private static void heapif(int[] arr, int i, int size){
int left = 2*i + 1;
int right = 2*i + 2;
int largest = i;
while (left < size){
if (arr[left] > arr[largest]){
largest = left;
}
if (right < size && arr[right] > arr[largest]){
largest = right;
}
if (largest != i){
swap(arr, i, largest);
} else {
break;
}
i = largest;
left = 2*i + 1;
right = 2*i + 2;
}
}
public static void main(String[] args) {
int[] arr = {8,6,1,2,7,9,11,0};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
输出：
D:\java\bin\java.exe
[0, 1, 2, 6, 7, 8, 9, 11]
