步骤：1，找最大堆（自右往左比较子节点，自下往上比较子节点和父节点）。2，交换根节点和尾部节点，并且不再比较交换下来的最大节点。
0，4，7，2，1，8，6，3，5
上述数列中：0不排进树节点。数列长度为9，父节点为4，父节点的索引为1，2，3，4
左边子节点索引为父节点索引的2倍，右边子节点索引为父节点的2倍+1.
public class HeapSort {
public static void main(String[] args) {
int[] ints = {0, 4, 7, 2, 1, 8, 6, 3, 5};
heapSort(ints);
for (int i = 0; i < ints.length; i++) {
System.out.println(ints[i]);
}
}
public static void heapSort(int[] ints) {
//标记最后一个数
int end = ints.length;
//end大于2，表示存在字节点
while (end > 2) {
//查找最大堆，遍历父节点，通过父节点找到子节点，完成三者比较
for (int i = (end - 1) / 2; i >= 1; i--) {
//假设最大索引在左边子节点，因为右边子节点可能不存在
int maxIndex = 2 * i;
//如果右边子节点存在，并且大于左边子节点,那么改变最大索引为右边子节点
if ((maxIndex + 1) < end && ints[maxIndex + 1] > ints[maxIndex]) {
maxIndex++;
}
//最大子节点和父节点比较，如果大于父节点，则进行交换
if (ints[maxIndex] > ints[i]) {
int temp = ints[maxIndex];
ints[maxIndex] = ints[i];
ints[i] = temp;
}
}
//索引为0的点不参与，所以跟节点是索引为1的节点,交换根节点和尾节点
int data = ints[1];
ints[1] = ints[end - 1];
ints[end - 1] = data;
//交换完，则最后一个节点不在参与下次比较
end--;
}
}
}
//结果：
0
1
2
3
4
5
6
7
8
