什么是堆排序

堆排序是使用二叉堆这样强大的数据结构来实现的排序

回顾：二叉堆的特性

• 二叉堆本质上是一种完全二叉树
• 最大堆（最小堆）的堆顶是整个堆中的最大（最小）元素

原理

当我们删除一个最小堆的堆顶的时候是把堆顶的元素删除，并把最后一个元素拿到堆顶

这时如果我们不把堆顶元素删除，而是把堆顶和最后一个元素替换，并把堆的有效长度减1

之后向下调整67，使堆保持稳定

重复上述操作将现在有效长度内的最后一位和堆顶互换，有效长度再减1

向下调整堆顶，保持堆的稳定性

继续互换堆顶，有效长度减1

调整堆

重复上述操作

最后得到的这个堆就是按照从大到小的顺序排好的堆

又因为二叉堆的实现是数组，所以堆的存储是从小到大排好是数组

步骤

1. 把无序数组构建成二叉堆
2. 循环将堆顶元素和有效堆长度内的最后一个元素互换，并且每次循环将有效堆长度减1

代码（最大堆）

下沉调整

/**
 * 下沉调整
 * @param array     待调整的堆
 * @param parentIndex    要下沉的父节点
 * @param length    堆的有效长度
 */
public static void downAdjust(int[] array, int parentIndex, int length){
    // temp保存父节点的值，用于最后的赋值
    int temp = array[parentIndex];
    int childIndex = 2 * parentIndex + 1;
    where(childIndex < length - 1){
        // 如果有右孩子，且右孩子的值大于左孩子的值，则定位到右孩子
        if(childIndex + 1 < length - 1 && array[childIndex] > array[childIndex + 1]){
            childIndex++;
        }
        // 如果父节点小于任何一个孩子的值，直接跳出
        if(temp 《= array[childIndex])
            break;
        // 无需真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = childIndex * 2 + 1;
    }
    array[parentIndex] = temp;
}

堆排序

/**
 * 堆排序
 * @param array     待调整的堆
 */
public static void heapSort(int[ array){
    // 1.把无序数组构建成二叉堆
     /* array.length是长度，array.length - 1是最后一个元素的下标
       ((array.length - 1) - 1) / 2 是最后一个元素的父节点 */
    for(int i = (array.length-2)/2, i >= 0; i --){
        downAdjust(array, i, array.length);
    }

    /* 2.循环交换“堆顶元素”和“有效长度之内的最后一个元素”
    	每次循环都递减有效长度，并调整堆 */
    for(int i = array.length - 1; i > 0 ; i --){
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        // 调整堆
        downAdjust(array, 0, i);
    }
}

复杂度

空间复杂度

O(1)，因为我们只说排序算法的空间复杂度，建堆的空间复杂度是二叉堆的事，不关堆排序的事

时间复杂度

O（logn）

分析

• 二叉堆节点下(downAdjust)是堆排序算法的基础，如果有n个元素待排，下沉的最坏时间为二叉树的高度O(nlogn)

• 排序算法的步骤是：1.无序数组构建成二叉堆，2.循环交换堆顶和有效长度内堆尾元素

  • 第一步，把无序数组构建成二叉堆，循环次数n/2次（非叶子节点），每次循环调用downAdjust，总时间n/2*logn，时间复杂度**O(nlogn)**
  • 第二步，需要进行n-1次循环。每次循环调用一次downAdjust方法，总时间（n-1）*logn，时间复杂度 O（nlogn）
  • 所以总时间复杂度为**O（nlogn）**

堆排序与快速排序

• 相同点
  • 平均时间复杂度都是**O（nlogn）**
  • 都是不稳定排序
• 不同点
  • 快速排序的最坏时间复杂度为O(n^2)，堆排序最坏时间复杂度稳定在O(logn)
  • 快速排序的递归和非递归方法的空间复杂度都是O(n)，堆排序的空间复杂度为O(1)

---

参考：小灰程序员-漫画：什么是堆排序