概述

介绍堆排序之前, 要先介绍什么是堆以及最大堆最小堆

什么是堆

这里的堆指的不是堆栈中的堆, 而是一种数据结构.

堆可以视为一棵完全的二叉树,完全二叉树的一个"优秀"的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素, 如下所示:

最大堆

最大堆就是堆中每个父节点的元素值都大于等于其孩子结点（如果存在）,这样的堆就是一个最大堆

显而易见, 最大堆中的最大元素值出现在根结点(堆顶)

最小堆

最小堆就是堆中每个父节点的元素值都小于等于其孩子结点（如果存在）,这样的堆就是一个最小堆

因此,最小堆中的最小元素值出现在根结点(堆顶)

数组的索引与节点的关系

parent(i) = (i-1)/2 向下取整
left(i) = 2i+1
rigth(i) = 2i+2

堆排序的思路

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

堆排序的时间空间复杂度如下:

Java代码实现

代码如下, 就是上边思路的实现.注释已经很详细了.

/**
 * 堆排序实现数组排序, 从小到大顺序
 * @param arr
 */
public static void heapSort(int[] arr) {
    /**
     * 1. 将堆调整为最大堆
     * 2. 将堆顶元素与末尾元素交换
     * 3. 重新调整堆, 并将堆顶元素与末尾元素交换
     * 4. 重复执行第三步, 直到只剩一个元素
     */
    // 构建最大堆, 从第一个非叶子结点向前, 依次进行构建, 最终生成最大堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        // 从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr, i, arr.length);
    }
    // 进行堆排序
    for (int j = arr.length - 1; j > 0; j--) {
        // 将堆顶元素与末尾元素进行交换
        int tmp = arr[0];
        arr[0] = arr[j];
        arr[j] = tmp;
        // 重新对堆进行调整,将最大值提到堆顶
        adjustHeap(arr, 0, j);
    }

}

/**
 * 调整最大堆, 假设子结构 最大堆已经构建
 * 
 * @param arr
 * @param i
 *          需要调整的结点
 * @param length
 *          当前数组的长度
 */
private static void adjustHeap(int[] arr, int i, int length) {
    /**
     * 1. 从当前结点的左子结点开始查找
     * 2. 若右子结点大就使用右子节点
     * 3. 若子结点大于当前元素, 令子结点往上冒
     * 4. 循环找到最后的大于当前元素的叶子结点
     * 5. 将当前元素放到为他空出来的位置
     */
    // 先取出当前元素i
    int tmp = arr[i];
    // 从i结点的左子结点开始，也就是2i+1处开始
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
        // 如果左子结点小于右子结点，k指向右子结点
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            k++;
        }
        // 如果子节点大于当前元素, 令其往上冒
        if (arr[k] > tmp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    // 将temp值放到最终的位置
    arr[i] = tmp;
}