原始堆如下：
image
堆排序算法
-
构造初始堆，从最后一个非叶节点开始调整
-
选出叶子节点中比自己大的一个交换，如果交换后的叶子节点不满足堆，则继续调整。
image20和16交换后导致16不满足堆的性质，因此需重新调整
image
-
-
构造好初始堆之后，将堆头元素交换到堆尾，堆尾的元素就已经是有序的了，然后一直重复，直到所有都有序。
20已经是最大的了，把交换到堆尾
image然后再从根节点3开始调整，然后每次挑出最大的放到堆尾，直至所有元素有序
image
Java代码如下：
/**
* @author: gethin
* @create: 2018-05-23 16:21
* @description: 常用排序算法
**/
public class Sort {
public static void main(String[] args) {
int[] nums = {16,7,3,20,17,8};
headSort(nums);
for (int num : nums) {
System.out.print(num + " ");
}
}
/**
* 堆排序
*/
public static void headSort(int[] list) {
//构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
for (int i = (list.length) / 2 - 1; i >= 0; i--) {
headAdjust(list, list.length, i);
}
//排序，将最大的节点放在堆尾，然后从根节点重新调整
for (int i = list.length - 1; i >= 1; i--) {
int temp = list[0];
list[0] = list[i];
list[i] = temp;
headAdjust(list, i, 0);
}
}
private static void headAdjust(int[] list, int len, int i) {
int k = i, temp = list[i], index = 2 * k + 1;
while (index < len) {
if (index + 1 < len) {
if (list[index] < list[index + 1]) {
index = index + 1;
}
}
if (list[index] > temp) {
list[k] = list[index];
k = index;
index = 2 * k + 1;
} else {
break;
}
}
list[k] = temp;
}
}
堆排序结果图：
image
