堆排序

堆排序基本介绍

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。
2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。注意：没有要求结点的左孩子的值和右孩子的值的大小关系。
3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4. 一般升序采用大顶堆，降序采用小顶堆

堆排序的实现思路

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

那么我们如何将待排序序列构造成一个大顶堆？

1. 设结点个数为n（即数组长度为n），则最后一个非叶子结点的下标为n/2-1
2. 判断此节点的值是否大于左右子树的值，是则需要交换。
3. 依次向前重复2过程，直到n=0，即到根结点
4. 因为向前重复的过程中可能存在改变了左右孩子的值的情况，从而影响了下面的树，所以在每次循环中，都要向下进行验证，保证每个父结点的值都大于左右孩子的值。

堆排序的代码实现

public static void heapSort(int[] arr) {
    int temp;
    // 自下而上初始化堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        buildHeap(arr, i, arr.length);
    }
    // 取最值进行交换
    for (int j = arr.length - 1; j > 0; j--) {
        // 保存数组最后一个元素
        temp = arr[j];
        // 将最后一个元素和堆顶元素进行交换
        arr[j] = arr[0];
        arr[0] = temp;
        buildHeap(arr, 0, j);
    }
}
/**
 * @param arr    表示待处理地数组
 * @param i      表示处理的非叶子结点的位置
 * @param length 表示需要处理的长度
 */
public static void buildHeap(int[] arr, int i, int length) {
    int temp = arr[i];
    // 每次调整都是自上而下的
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
        if (k + 1 < length && arr[k + 1] > arr[k]) {
            k++;
        }
        if (arr[k] > temp) {
            arr[i] = arr[k];
        } else {
            break;
        }
        i = k;
        arr[i] = temp;
    }
}