堆排序

构建堆：

插入的第index个元素与其父比较，如果大，则交换，然后继续与其父交换。

public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

调整堆：

找到两个孩子，与大的交换，直到超出堆的大小

public static void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1;
    while (left < heapSize) {
         // 左右中较大的
        int largest = left + 1 > heapSize && arr[left + 1] < arr[left] ? left + 1 : left;
        largest = arr[index] > arr[largest] ? index : largest;
        // 如果index最大，则不需要交换
        if (index == largest) {
            break;
        }
        // 找到两个孩子，与大的交换
        wap(arr, index, largest);
        // 继续while
        index = largest;
        left = index * 2 + 1;
    }
}

堆排序：

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

堆是无序的，构建完堆后，将堆顶与最后一个元素交换，堆的大小减1，则数组中最后一个元素是最大值，循环，调整堆，大小减1，则倒数第二个，倒数三个······

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 1) {
        return;
    }
    // 构建大根堆
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
    // // 堆顶为最大值，堆顶与堆的最后一个交换，heapify 之后堆顶为最大，
    // 最大值为最后一个
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
}

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。