C++排序算法之堆排序

超、凢脫俗 2022-06-12 02:36 168阅读 0赞

**堆排序算法**

**1、算法介绍**

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

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

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

**2、执行过程**

例如：

原始序列： 49 38 65 97 76 13 27 49

（1）建堆

先将这个序列调整为一个大顶堆。原始序列对应的完全二叉树如下图所示

![Center][]

![Image 1][]

在这个完全二叉树中，结点76、13、27、49是叶子结点，它们没有左右孩子，所以它们满足堆的定义。从97开始，按照97、65、38、49的顺序依次调整。

1.  调整97。97>49，所以97和它的孩子49 满足堆的定义，不需要调整。
2.  调整65。65>13，65>27，所以65和它的孩子13、27满足堆的定义，不需要调整。
3.  调整38。97>38，76>38，不满足堆的定义，需要调整。在这里，38的两个孩子结点值都比38大，应该和哪个交换呢？显然应该是和两者中最大的交换啊。如果和76交换，则76<97仍然不满足堆的定义。因此，将38和97交换，交换后38成了49的根结点，49>38，仍然不满足，需要继续调整，将38和49交换，结果如下图

![Center 1][]

![Image 1][]

1.  调整49。49<97，49<65不满足定义，需要调整。因此和97交换，交换后49<76仍不满足堆的定义，继续调整，将49和76交换，结果如下图

![Center 2][]

![Image 1][]

（2）排序

可以看到，此时已经建立好了一个大顶堆。对应的序列为：97 76 65 49 49 13 27 38。将堆顶记录97和序列最后一个记录38交换。第一趟堆排序完成。97到达其最终的位置。将除97外的序列38 76 65 49 49 13 27重新调整为大顶堆。现在这个堆只有38不满足堆的定义，其他的记录都满足，所以只需要调整一个38就足够了。

调整38，结果如下图

![Center 3][]

![Image 1][]

现在的序列为76 49 65 38 49 13 27 97。将堆顶记录76和最后一个记录27交换，第二趟堆排序完成，76到达其最终位置，此时序列如下：27 49 65 38 49 13 76 97.然后对除76和97的序列依照上面的方法继续处理，知道树中只剩下1个结点时排序完成。

**堆排序算法过程描述：**

**（1）从无序序列所确定的完全二叉树的第一个非叶子结点开始，从右至左，从下至上，对每个结点进行调整，最终将得到一个大顶堆；**

**对结点的调整方法： 当前节点的值（假设为a）与其孩子结点进行比较，如果存在大于a的孩子结点，则从中选出最大的一个与a交换。****当a来到下一层的时候重复上述操作，直到a的孩子结点值都小于a的值为止。**

**（2）将当前无序序列中第一个元素，反映在树中是根结点（假设为a）与无需序列中最后一个元素交换（假设为b）。a进入有序序列，****到达最终位置。无序序列中元素减少1个，有序序列中元素增加1个。此时只有结点b可能不满足堆的定义，对其进行调整。**

**（3）重复（2）中过程，直到无序序列中的元素剩下1个时排序结束。**

**代码实现如下：**

#include <iostream>
    #include <vector>
    using namespace std;
    
    /*该函数完成对在数组R[low]到R[high]范围内，对在low上的结点进行调整（大堆）*/
    void heapAdjust(int R[], int low, int high)
    {
    	int i = low;
    	int j = i *2+1;          //R[j]是R[i]的左孩子节点 （此时对应数组从0开始，若从1开始则 j=i*2）
    	int temp = R[i];
    	while (j < high)
    	{
    		if (j < high&&R[j] < R[j + 1])                 
    			++j;                                   //若右孩子较大，则把 j 指向右孩子
    		if (temp < R[j])
    		{
    			R[i] = R[j];                           //将 R[j] 调整到双亲节点的位置上
    			i = j;                                 //修改 i 和 j 的值，以便继续向下调整
    			j = 2 * i+1;
    		}
    		else
    			break;
    	}
    	R[i] = temp;
    }
    
    /*堆排序函数*/
    void heapSort(int R[], int n)
    {
    	int i;
    	int temp;
    	for (i = n / 2-1; i >= 0; --i)             //建立初始堆（大顶堆）（此时对应的数组下标从0开始，若从1开始第一个非叶子结点为 i=n/2）
    		heapAdjust(R, i, n-1);
    	for (i = n-1; i >= 1; --i)                  //进行 n-1 次循环，完成堆排序
    	{
    		/*此交换将根结点元素刚入最终的位置上*/
    		temp = R[0];
    		R[0] = R[i];
    		R[i] = temp;
    		heapAdjust(R, 0, i - 1);            //在较少了 1 个元素的无序序列中进行调整
    	}
    }
    
    void main()
    {
    	int R[8] = {49,38,65,97,76,13,27,49 };
    	heapSort(R, 8);
    	for (int i = 0; i < 8; i++)
    		cout << R[i] << " ";
    	cout << endl;
    }

运行结果如下：

**![Center 4][]**

**复杂度分析：**

**（1）时间复杂度**

最好情况=最坏情况=平均情况=O(nlogn)

**（2）空间复杂度**

只需要一个额外的temp，因此空间复杂度为O(1)。

**总结：**堆排序在最坏情况下的时间复杂度也是O(nlogn)，这是它相对于快速排序的最大优点。堆排序的空间复杂度为O(1)，在所有时间复杂度为O(nlogn)的排序中是最小的，这也是其一大优点。堆排序适合的场景是记录数很多的情况，典型的例子是从10000个记录中选出前10个最小的（或最大的），这种情况用堆排序最好，如果记录数少，不提倡使用堆排序。

[Center]: /images/20220612/d41d757d528449cc95f074871115c446.png
[Image 1]: 
[Center 1]: /images/20220612/545f14e73b25410c8852b9a1891608d9.png
[Center 2]: /images/20220612/165f1ca8af1b4cccb6efbe24c8d485fa.png
[Center 3]: /images/20220612/c03cffe36cf948cd93c9e737d54d3efb.png
[Center 4]: /images/20220612/3b9d70575bf042848b1286d698a6e716.png