堆排序

堆排序代码如下：

    public static void main(String[] args) {
        System.out.println("原数组：");
        int[] arr = { 10, 8, 15, 16, 6, 9, 1, 7, 11, 20, 12, 5 };//示例数组
        System.out.println(Arrays.toString(arr));
        
        // 定义开始调整的位置
        int startNode = (arr.length - 1) / 2;
        for (int i = startNode; i >= 0; i--) {
            getArrayToHeap(arr, arr.length, i);
        }
        // 调整为大顶推的数组
        System.out.println("大顶推数组：" + "\n" + Arrays.toString(arr));
        
        //对大顶堆进行排序，把堆的根元素和最后一个元素进行调换
        for (int i = arr.length-1; i > 0 ; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            getArrayToHeap(arr, i, 0);
        }
        System.out.println("最终的堆排序：" + "\n" + Arrays.toString(arr));
    }

    /**
     * 创立一个数组转堆的方法（大顶推）
     * 
     * @param arr   需要调整的数组
     * @param a     数组中元素的个数
     * @param index 开始调整的位置
     */
    public static void getArrayToHeap(int[] arr, int a, int index) {
        // 获取左右节点的位置
        int liftNode = 2 * index + 1;
        int rightNode = 2 * index + 2;
        // 查找最大节点对应的位置
        int maxNode = index;
        if (liftNode < a && arr[liftNode] > arr[maxNode]) {
            maxNode = liftNode;
        }
        if (rightNode < a && arr[rightNode] > arr[maxNode]) {
            maxNode = rightNode;
        }
        // 对最大节点进行调换位置
        if (maxNode != index) {
            int temp = arr[maxNode];
            arr[maxNode] = arr[index];
            arr[index] = temp;
            // 防止调整后的堆不是大顶堆，重新调用方法
            getArrayToHeap(arr, a, maxNode);
        }
    }

输出结果：

原数组：
[10, 8, 15, 16, 6, 9, 1, 7, 11, 20, 12, 5]
大顶推数组：
[20, 16, 15, 11, 12, 9, 1, 7, 10, 6, 8, 5]
最终的堆排序：
[1, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, 20]

注意：在查找最大节点的时候，if语句里如果不加入 liftNode < a 和 rightNode < a ，那么在节点增多的情况下，会出现数组索引越界异常：<u>java.lang.ArrayIndexOutOfBoundsException</u> 。