堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

描述：

1、用数组创建一个最大堆（子结点的键值或索引总是小于它的父节点），如果二叉树中父节点比子节点小，则交换位置，注意交换后下面的子树规则可能被破坏，所以要循环至叶子节点。
2、此时数组中的第一个元素就是最大堆的根节点，也就是最大的元素。
2、将最大堆的根节点取出和最后一个元素交换，放在数组最后，剩下的元素继续创建最大堆，重复至排序完成。

动画：

堆排序.gif

代码：

    private void heapSort(int[] array) {
        //先创建最大堆
        int length = array.length;
        //length / 2 - 1是完全二叉树最后一个非叶子节点
        //从最后一个非叶子节点开始整理，直到根节点（下标0）
        for (int i = length / 2 - 1; i >= 0; i--) {
            maxHeapify(array, i, length - 1);
        }
        for (int i = length - 1; i > 0; i--) {
            //下标为0的元素为根节点且最大，取出放到最后
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            //剩下的继续整理
            maxHeapify(array, 0, i - 1);
        }
    }

    /**
     * 整理最大堆
     * @param array 数组
     * @param start 起点下标
     * @param end 最后一个叶子节点下标
     */
    private void maxHeapify(int[] array, int start, int end) {
        int parent = start;
        //左孩子下标是父节点的2倍加1
        int child = parent * 2 + 1;
        while (child <= end) {
            //child + 1 表示右孩子
            //如果有右孩子 且 左孩子小于右孩子  则记录大的那个（这里加=号是保证排序稳定）
            if (child + 1 <= end && array[child] <= array[child + 1]) {
                child++;
            }
            if (array[parent] > array[child]) {
                return;
            } else {
                //交换父子节点
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                //继续将子节点作为父节点整理
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }