最近又要回顾一下各类排序算法，堆排序，一个时间复杂度不太稳定的算法，根据完全二叉树的特性来建立算法过程。
步骤
- 调整一轮大顶堆，把最大值调至顶部节点。此时所有叶子节点应该都小于其父节点（父节点大于子节点的调整）
- 将顶部节点（最大值）与最后叶子节点替换
- 排序指针指向倒数第二个叶子节点，继续调整一轮大顶堆
- 重复2，3步骤
简单来说，结果就是每轮把最大值调整到本轮里最后一个叶子节点，来完成排序过程。
上代码（java）
public class HeapSort
{
public HeapSort(int[] list) {
//{4,6,3,1,7,9,2,5,11,8,10}
this.list = list;
}
public void execute() {
int[] result = HeapSort.StartSort(this.list); //将初始化数组传入
//this.show(result);
}
public static int[] StartSort(int[] array) {
len = array.length;
if (len < 1) return array;
//1.构建一个最大堆
buildMaxHeap(array);
//打印出每步的构建过程
for(int i : array) {
System.out.print(i + ",");
}
System.out.println("");
//2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
while (len > 0) {
swap(array, 0, len - 1);
len--;
adjustHeap(array, 0);
for(int i : array) {
System.out.print(i + ",");
}
System.out.println("");
}
return array;
}
public static void buildMaxHeap(int[] array) {
//从最后一个非叶子节点开始向上构造最大堆
for (int i = (len/2 - 1); i >= 0; i--) {
adjustHeap(array, i);
}
}
public static void adjustHeap(int[] array, int i) {
int maxIndex = i;
int left_c = (i + 1) * 2 - 1;
int right_c = (i + 1) * 2;
//如果有左子树，且左子树大于父节点，则将最大指针指向左子树
if ( left_c < len && array[left_c] > array[maxIndex]) {
maxIndex = left_c;
}
//如果有右子树，且右子树大于父节点，则将最大指针指向右子树
if ( right_c < len && array[right_c] > array[maxIndex]) {
maxIndex = right_c;
}
//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
if (maxIndex != i) {
swap(array, maxIndex, i);
adjustHeap(array, maxIndex);
}
}
}
代码参考
https://www.cnblogs.com/guoyaohua/p/8600214.html
这个作者的堆排序似乎有问题，adjustHeap函数，起始的左右节点的位置不对。导致有几位并没有排序成功。
