用数组表示二叉树，并实现堆排序

步骤：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