数据结构之浅析堆排序

阳光穿透心脏的1/2处 2022-09-28 13:02 187阅读 0赞

# 堆排序 #

*  **定义**
 *  **实现**
 *  **复杂度分析**

## 1、定义 ##

> 将待排序的序列构造成一个大顶堆（整个序列的最大值就是堆顶的根节点），然后将根节点与堆中末尾元素交换，再将剩余的n-1个序列重新构造成一个堆，从而又得到n个元素的次大值，如此反复就能得到一个有序序列。

1、如下图所示，是一个大顶堆，90是最大值，将根节点（90）和末尾元素（20）互换。

![这里写图片描述][SouthEast]

2、此时90成为了整个堆中的最后一个元素，然后将剩下的n-1个元素重新构造大顶堆，再重复步骤1，如下图所示：

![这里写图片描述][SouthEast 1]

3、如此循环下去，最终就会得到有序的序列。

## 2、实现 ##

> 1、如何由一个无序的序列构造成一个大顶堆  
> 2、如果在输出堆顶元素后，如何调整剩余元素成为一个新堆

对顺序表L进行堆排序的程序：

void HeapSort(SqList *L)
    {
        int i;
    
        //构建一个大顶堆
        for(i = L->length/2 ; i>0 ; i--)
            HeapAdjust(L,i,L->length);
    
        for(i=L->length ; i>1 ; i--)
        {
            swap(L,1,i);
            HeapAdjust(L,1,i-1);
        }
    
    }

整个排序过程主要由两个过程完成（两个循环），第一个循环是将现有的待排序的序列构建成为一个大顶堆；第二个循环是将根节点和末尾元素交换，然后将剩余的元素重新构造大顶堆。

> 下面将详细分析函数HeapAdjust（）的实现

void HeapAdjust(SqList*L, int s, int m)
    {
        int temp, j;
        temp = L->r[s];
        for (j = 2 * s; j <= m; j *= 2) //沿关键点较大的子节点筛选
        {
            if (j < m && L->[j] < L->[j + 1]) //得到哪一个父节点的哪一个子节点较大
                ++j;  //取出较大的子节点编号
            if (temp >= L->r[j])  //判断是否比其父节点大，如果最大的子节点都比父节点小，则退出
                break;
            L->r[s] = L->r[j];  //下面三行都是为了实现父节点和最大子节点的交换（比父节点大时）
            s = j;
        }
        L->r[s] = temp;
    }

1、如下图所示，节点4（父节点）比节点8（左子节点）小，需要交换

![这里写图片描述][SouthEast 2]

2、交换的结果如下图所示：

![这里写图片描述][SouthEast 3]

3、由于节点3（父节点）比其左右子节点都大，所以不需要交换。节点2（父节点）比其子节点4,5都小，找出最大的是右子节点，所以和右子节点交换。

![这里写图片描述][SouthEast 4]

4、如此循环，最终得到的大顶堆如下图所示：

![这里写图片描述][SouthEast 5]

> 然后进行堆排序的第二个循环（根节点与末尾节点交换，对n-1再使用上述的调整），就可以得到最终的有序结果。

## 3、复杂度分析 ##

> 堆排序的运行时间主要是消耗在初始构建堆和重建堆时的反复筛选上。空间复杂度上，使用一个暂存单元，所以为1.

1、构建堆的时间：  
在构建堆的过程中，是完全二叉树从最下层最右边的非终端节点开始构造的（n/2）个，将其与左右子节点的比较是必要的，并且最多进行2次比较和互换的操作，因此其时间复杂度为O（n）。

1、重建堆的时间：  
第i次取堆顶记录重建堆需要用O（logi）的时间，并且需要取n-1次堆顶，因此，重建堆的时间复杂度为O（nlogn）。

所以整体的时间复杂度为O（nlogn）。由于堆排序对于原始数据的排序状态不敏感，所以无论是最好、最坏还是平均都是这个时间复杂度。

[SouthEast]: /images/20220708/ee51c12d957746bfb0a111f5c3768d28.png
[SouthEast 1]: /images/20220708/f796045064854774ada49565e34128b4.png
[SouthEast 2]: /images/20220708/9d3ff06c5e834c719d151f4370068107.png
[SouthEast 3]: /images/20220708/ff0fe718539446b6880e9ec5fd3d2164.png
[SouthEast 4]: /images/20220708/863d5d49c71143dcac25296f25aca7c6.png
[SouthEast 5]: /images/20220708/6e1612fb08ec49e5a771ed7667e9fa90.png