public class HeapSort {

    /**
     * 采用最大堆升序排序数组
     * @param array 已经构建好但未排序的二叉堆数组
     * @param border 数组边界,此边界指向最想最后一个“删除”的数据
     *(即在数组中最左侧的“删除”数据)。初始值为数组的长度length。
     */
    public static void heapSort(int[] array,int border){
        int n = 1;
        while (border > 0){
            //”删除“数组首元素
            int temp = array[0];
            //--border:border的初始值为数组的长度length,因此先--,再赋值。
            // 不能使用border--,否则会下标越界错误。
            // 或者采用border=array.length-1,则此处改为border--
            array[0] = array[--border];
            array[border] = temp;
            //调整二叉堆
            System.out.println("---------------------第" + n + "次构建二叉堆---------------------");
            System.out.println(Arrays.toString(array));
            System.out.println("---------------------调整二叉堆--------------------------");
            downAdjust(array,border);
            System.out.println("-------------------第" + n++ + "次构建二叉堆结束-------------------\n");
        }
    }

    /**
     * 下沉调整
     * @param array 待调整数组
     * @param border 数组边界,此边界指向最想最后一个“删除”的数据(即在数组中最左侧的“删除”数据)
     */
    private static void downAdjust(int[] array,int border){
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 2*parentIndex + 1;
        while (childIndex  < border){
            //父节点小于或等于子节点,且右子节点大于左子节点,子节点下标定位到右子节点
            if (childIndex + 1 < border && array[childIndex] < array[childIndex + 1]){
                ++childIndex;
            }
            //父节点大于子节点,直接退出循环。注意:这里只能用temp,而不是array[parentIndex]。
            // 因为采用的是单向覆盖,所以array[parentIndex]实际上还是原先的array[childIndex],
            // 而逻辑上array[parentIndex]应该是被temp存储的值所覆盖的
            if (temp > array[childIndex]){
                break;
            }

            //下沉,子节点单向覆盖父节点
            array[parentIndex] = array[childIndex];
            //更新父节点和子节点下标
            parentIndex = childIndex;
            childIndex = 2*parentIndex + 1;
            System.out.println(Arrays.toString(array));
        }
        //最初父节点的值,覆盖其调整后的实际位置
        array[parentIndex] = temp;
    }

    public static void main(String[] args) {
        //array为构建好的最大堆。使用无序数组时,需要调用构建二叉堆的方法,将无序数组构建成最大堆
        int[] array = new int[]{10,8,9,7,5,4,6,3,2};
        heapSort(array,array.length);
        System.out.println(Arrays.toString(array));
    }

}
---------------------第1次构建二叉堆---------------------
[2, 8, 9, 7, 5, 4, 6, 3, 10]
---------------------调整二叉堆-------------------------
[9, 8, 9, 7, 5, 4, 6, 3, 10]
[9, 8, 6, 7, 5, 4, 6, 3, 10]
-------------------第1次构建二叉堆结束-------------------

---------------------第2次构建二叉堆---------------------
[3, 8, 6, 7, 5, 4, 2, 9, 10]
---------------------调整二叉堆-------------------------
[8, 8, 6, 7, 5, 4, 2, 9, 10]
[8, 7, 6, 7, 5, 4, 2, 9, 10]
-------------------第2次构建二叉堆结束-------------------

---------------------第3次构建二叉堆---------------------
[2, 7, 6, 3, 5, 4, 8, 9, 10]
---------------------调整二叉堆-------------------------
[7, 7, 6, 3, 5, 4, 8, 9, 10]
[7, 5, 6, 3, 5, 4, 8, 9, 10]
-------------------第3次构建二叉堆结束-------------------

---------------------第4次构建二叉堆---------------------
[4, 5, 6, 3, 2, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[6, 5, 6, 3, 2, 7, 8, 9, 10]
-------------------第4次构建二叉堆结束-------------------

---------------------第5次构建二叉堆---------------------
[2, 5, 4, 3, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[5, 5, 4, 3, 6, 7, 8, 9, 10]
[5, 3, 4, 3, 6, 7, 8, 9, 10]
-------------------第5次构建二叉堆结束-------------------

---------------------第6次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[4, 3, 4, 5, 6, 7, 8, 9, 10]
-------------------第6次构建二叉堆结束-------------------

---------------------第7次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[3, 3, 4, 5, 6, 7, 8, 9, 10]
-------------------第7次构建二叉堆结束-------------------

---------------------第8次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
-------------------第8次构建二叉堆结束-------------------

---------------------第9次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
-------------------第9次构建二叉堆结束-------------------

[2, 3, 4, 5, 6, 7, 8, 9, 10]