MENU

Catalog

    排序(3):堆排序

    June 7, 2018 • 文章

    系列文章目录

    排序(1):直接插入排序,二分查找插入排序,希尔排序
    排序(2):快速排序
    排序(3):堆排序
    排序(4):归并排序
    排序(5):基数排序
    排序(6):总结

    堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。

    堆实际上是一棵完全二叉树,其满足性质:任何一结点大于等于或者小于等于其左右子树结点。

    堆分为大顶堆和小顶堆,满足“任何一结点大于等于其左右子树结点”的称为大顶堆,满足“任何一结点小于等于其左右子树结点”的称为小顶堆。由上述性质可知:大顶堆的堆顶肯定是最大的,小顶堆的堆顶是最小的。

    下面举个例子(资源来自堆排序-海子)来说明堆排序的过程(以升序为例):

    (1)

    给定整型数组:{ 16, 7, 3, 20, 17, 8 },根据该数组“构建”完全二叉树(并不是真的写代码去构建,只是把数组看成完全二叉树去操作)。

    程序从最后一个非叶子结点开始,即3。判断其左右孩子:8,8比3大,把8调整上去。

    (2)

    3结点下无孩子,判断结束。

    继续往前一步,至7结点,判断其左右孩子:20和17,20是最大的,将其调整上去。

    (3)

    7结点下无孩子,判断结束。

    继续往前一步,至16结点,判断其左右孩子:20和8,20是最大的,将其调整上去。

    (4)

    判断16结点下左右孩子:7和17,17是最大的,将其调整上去。

    (5)

    16结点下无孩子,判断结束。

    遍历已至头部,结束。

    (6)至此数组已经满足大顶堆的性质,接下来的操作就很简单了。

    看完上面所述的流程你至少有两个疑问:

    • 如何确定最后一个非叶子结点?

      其实这是有一个公式的,设二叉树结点总数为n,则最后一个非叶子结点是第$⌊\frac n2⌋$个。

    • 数组当中如何确定当前结点的左右孩子位置?

      设当前结点下标是i,则其左孩子的下标是2i,右孩子的下标是2i+1。请注意:这是建立在数组下标从1开始的情况。若数组下标从0开始,则其左右孩子下标还各需多加一个1。

    以下代码默认数组下标从1开始,请读者注意。

    /* 已知 array[left]...array[right] 的值除 array[left] 之外均满足堆的定义,
    本函数调整 array[left],使 array[left]...array[right] 成一个大顶堆 */
    void HeapAdjust(int array[], int left, int right)
    {
        int index = left;
      
        for (int i = left * 2; i <= right; i = i * 2)
        {
            if (i < right && array[i] < array[i + 1])  // 找到孩子中较大者
                i++;
            if (array[index] >= array[i])
                return;
            swap(array[index], array[i]);
            index = i;
        }
    }
    
    void HeapSort(int array[], int left, int right)
    {
        int len = right - left + 1;
      
        for (int i = len / 2; i >= left; i--)  // 把数组调整成大顶堆
            HeapAdjust(array, i, right);
      
        for (int i = right; i > left; i--)     // 排序
        {
            swap(array[left], array[i]);
            HeapAdjust(array, left, i - 1);
        }
    }

    时间复杂度为$O(nlogn)$,证明如下。

    首先计算建堆的时间,也就是下面的代码,

    for (int i = len / 2; i >= left; i--)  // 把数组调整成大顶堆
        HeapAdjust(array, i, right);

    n个结点,从第0层至第$log_2n$层。对于第i层的$2^i$个点如果需要往下走$log_2n-i$步,那么把走的所有步相加得,
    $$
    \begin{align}
    T(n)&=\sum_{i=0}^{i=log_2n}{2^i(log_2n-i)}\\
    &=2n-log_2n-2\\
    &<2n\\
    &=O(n)
    \end{align}
    $$

    接下来就是排序的时间,即下面的代码:

    for (int i = right; i > left; i--)  // 排序
    {
        swap(array[left], array[i]);
        HeapAdjust(array, left, i - 1);
    }

    HeapAdjust()耗时$logn$,共n次,故排序时间为$O(nlogn)$。

    综上所述,堆排序时间复杂度为$T(n)=O(n)+O(nlogn)=O(nlogn)$。

    Archives QR Code Tip
    QR Code for this page
    Tipping QR Code