深入浅出排序算法之堆排序

1. 算法介绍

2. 执行流程⭐⭐⭐⭐⭐✔

3. 代码实现

4. 性能分析

1. 算法介绍

堆是一种数据结构，可以把堆看成一棵完全二叉树，这棵完全二叉树满足：任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小，则这样的堆叫作大顶堆;若父亲小孩子大，则这样的堆叫作小顶堆。

根据堆的定义知道，代表堆的这棵完全二叉树的根结点的值是最大(或最小)的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大(或最小)值，然后将找出的这个值交换到序列的最后(或最前)，这样，有序序列关键字增加1个，无序序列中关键字减少1个，对新的无序序列重复这样的操作，就实现了排序。这就是堆排序的思想。

堆排序中最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树。

2. 执行流程⭐⭐⭐⭐⭐✔

建堆是先从自下而上，从右往左建

初始堆的每一个结点都要满足堆的定义，也就是父节点的值大于左右孩子结点的值！！！

选出最大值，是将根结点和最后一个结点互换，然后继续构建大顶堆！！！

⭐⭐⭐堆顶和最后一个元素交换，才算一趟，也是该趟的最终序列结果！！！

建堆和排序结果是两个阶段，但同属于一趟中。

图示如下：

3. 代码实现

为了三个步骤：

步骤一：先建堆（大根堆或者小根堆）

步骤二：交完堆顶和最后一个元素，然后堆的大小减一

步骤三：向下调整堆

步骤一只需实现一次，步骤二和步骤三循环执行，得到最终的有序序列。

    //开始排序：堆排序分为三个功能 ①开始建堆，②交换，③向下调整，重复②和③步
    public static void heapSort(int[] array,int len){
        int end = len - 1;//确定最后一个结点的下标
        createHeap(array);//建堆
        //当只剩下一个结点的时候，就不需要交换
        while(end > 0){
            //交换
            swap(array,0,end);
            //向下调整
            shiftDown(array,0,end);
            //调整完一个结点，下一个
            end--;
        }
    }
    //交换数据
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //堆排序（大根堆）
    //从上往下建堆，所以先找父节点，再找孩子结点
    public static void createHeap(int[] array){
        for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){
            shiftDown(array,parent,array.length);
        }
    }
    //向下调整
    public static void shiftDown(int[] array,int parent,int len){
        //定义一个记录孩子下标的变量（左孩子）
        int child = 2 * parent + 1;
        //判断父节点和孩子结点的大小，至少左孩子要存在
        while(child < len){
            //比较左右孩子
            if((child + 1) < len && array[child] < array[child + 1]){
                child++;
            }
            //判断父节点和孩子节点
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {5,4,3,2,1};
        Sort.heapSort(a, a.length);
        for (int x : a) {
            System.out.print(x + " ");
        }
    }

4. 性能分析

时间辅助度	空间复杂度
O(N*logN)	O(1)
数据不敏感	数据不敏感

稳定性：不稳定。

来上解析，怎么计算这个时间复杂度。

（1）步骤一的时间复杂度：首先知道有N个结点开始建堆，这个时间复杂度就是O(N)，大家可以去看看这篇文章，里面有讲建堆的时间复杂度。链接如下：

数据结构——堆、堆排序和优先级队列（代码为Java版本）

（2）步骤二和步骤三循环的时间复杂度：那么我第一个结点交换时，需要向下调整为log(N - 1)层；交换第二个结点后，需要向下log(N - 2)，接下来就是log(N - 3)，log(N - 4)，……，log1。所以总的调整次数是log(N - 1) + log(N - 2) + log(N - 3) + log(N - 4) + …… + log1 = log((N - 1)!)。

我们可以在网上看到堆排序的时间复杂度是O(N*logN)，这是堆排序的大致估算（我们算时间复杂度都是算个大概），其实log((N - 1)!) 约等于 NlogN。下面是我的证明结果：

① 使用夹逼准则证明：

先求上限： $\log \left ( n!\right ) = \sum_{i = 1}^{n}\log \left ( i \right )\leqslant \sum_{i=1}^{n}\log \left ( n \right )=\log n^{n}=O\left (n\log n \right )$

再求下限:

因为 $n! \geqslant \left ( \frac{n}{2} \right )^{\frac{n}{2}}$

所以 $\log \left ( n! \right )\geqslant \log \left ( \frac{n}{2} \right )^{\frac{n}{2}}= \frac{n}{2}\log \frac{n}{2}= \frac{n}{2}\log n-\frac{n}{2}\log 2$

当 $n\geqslant 4$ 时， $\frac{n}{2}\log 2=\frac{1}{4}n\log 4\leqslant \frac{1}{4}n\log n$

② 则有：

$\log \left ( n! \right )\geqslant \frac{n}{2}\log n-\frac{n}{2}\log 2\geqslant \frac{n}{2}\log n-\frac{1}{4}n\log n=\frac{1}{4}n\log n\approx$ $\Omega \left ( n\log n \right )$