堆排序

介绍：堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为O(nlogn)，为不稳定排序
堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，不约束左右节点的大小关系
大顶堆特点：array[i]>=array[2i+1] && array[i]>=array[2i+2],i从0开始
排序规则：一般升序采用大顶堆，降序采用小顶堆
堆排思想（左→右下→上）

将待排序序列构造成一个大顶堆(数组)
此时，整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换，此时末尾就为最大值
然后将剩余n-1个元素重新构成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列
总结：可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序的序列了

代码块

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSortDemo {
    public static void main(String[] args) {
        int array[] = {4, 6, 8, 5, 9};
        heapSort(array);
    }

    /**
     * 堆排序
     *
     * @param array
     */
    public static void heapSort(int array[]) {
        System.out.println("堆排序~");
        int temp = 0; // 辅助交换
        // 分步完成
//        adjustHeap(array,1,array.length);
//        System.out.println("第一次~~~"+Arrays.toString(array));
//        adjustHeap(array,0,array.length);
//        System.out.println("第二次~~~"+Arrays.toString(array));

        /**
         * 最终代码
         * 功能：将待排序序列构造成一个大顶堆(数组)
         */
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }

        /**
         * 1. 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，不约束左右节点的大小关系
         * 2. 大顶堆特点：array[i]>=array[2i+1] && array[i]>=array[2i+2],i从0开始
         */
        for (int j = array.length - 1; j > 0; j--) {
            // 交换
            temp = array[j];
            array[j] = array[0]; // array[0]为最大值
            array[0] = temp;
            adjustHeap(array, 0, j);
        }
        System.out.println("排序后的结果~~~" + Arrays.toString(array));
    }

    /**
     * 将一个数组（二叉树），调整为大顶堆
     * 功能：完成将以i对应的非叶子节点的树调整成大顶堆
     * 举例：int array[] = {4,6,8,5,9};→i=1（6）
     *
     * @param array  待调整的数组
     * @param i      表示非叶子节点在数组中索引
     * @param length 表示对多少个元素进行调整，length逐渐减少
     */
    public static void adjustHeap(int array[], int i, int length) {
        int temp = array[i]; // 先取出当前数组值
        /**
         * 调整
         * k=2*i+1 为i的左子节点
         * k+1< length 提高效率
         */
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && array[k] < array[k + 1]) { //左节点小于右节点
                k++; // 指向右节点
            }
            if (array[k] > temp) { // 左子节点大于父节点
                array[i] = array[k]; // 把较大的值赋给当前节点
                i = k; // !!! i指向k,继续循环比较
            } else {
                break;
            }
        }
        // for循环结束后已经将i为父节点的树的最大值放在了最顶上（局部）
        array[i] = temp; // 将temp值放到调整后的位置
    }
}