八大排序算法-堆排序

雨点打透心脏的1/2处 2022-06-07 10:13 148阅读 0赞

在说堆排序之前，要先说明[二叉堆的概念][Link 1]。因为堆排序就是通过二叉堆来实现的。

注：以下说会用堆来作二叉堆的简称。至于堆的定义，大家可以自行查阅。

在了解完堆之后，我们知道堆有大根堆和小根堆的不同。我们先了解堆排序的思想，之后用一个大根堆来实现代码。

堆排序的定义是：利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征（这里我们用大根堆），调整数组的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n - 1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列，在当前无序区中选取最大（或最小）关键字的记录变得简单。

堆排序的基本思想：

简单一点就是堆排序就是不断的选出最小的值，然后放到有序区的排序方法。所以堆排序是选择排序的一种。  
既然堆排序用到了堆，那我们就必须要把排序的数组转化成堆的格式才能用得到堆的性质。  
所以，我们有两个步骤要做：  
一、建堆：建堆是不断调整堆的过程，从len/2处开始调用②，把从第len/2个结点为根的子树开始，该子树成为堆，之后向前依次对各结点为根的子树进行调整，使之成为堆，至根结点。该过程是线性的，时间复杂度为：O(n)。

二、调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大者，如果最大值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lg(n)的操作，因为是沿着深度方向进行调整的。

三、堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。

堆排序过程的时间复杂度是O(nlgn)。

因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。

算法：

//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
    //本函数功能是：根据数组array构建大根堆
    void HeapAdjust(int array[], int i, int nLength)
    {
    	int nChild;
    	int nTemp;
    	for (; 2 * i + 1<nLength; i = nChild)
    	{
    		//子结点的位置=2*（父结点位置）+1
    		nChild = 2 * i + 1;
    		//得到子结点中较大的结点
    		if (nChild<nLength - 1 && array[nChild + 1]>array[nChild])
    			++nChild;
    		//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
    		if (array[i]<array[nChild])
    		{
    			nTemp = array[i];
    			array[i] = array[nChild];
    			array[nChild] = nTemp;
    		}
    		else break; //否则退出循环
    	}
    }
    //堆排序算法
    void HeapSort(int array[], int length)
    {
    	int i;
    	//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    	//length/2-1是最后一个非叶节点，此处"/"为整除
    	for (i = length / 2 - 1; i >= 0; --i)
    		HeapAdjust(array, i, length);
    	//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    	for (i = length - 1; i > 0; --i)
    	{
    		//把第一个元素和当前的最后一个元素交换，
    		//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
    		array[i] = array[0] ^ array[i];
    		array[0] = array[0] ^ array[i];
    		array[i] = array[0] ^ array[i];
    
    		//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
    		HeapAdjust(array, 0, i);
    	}
    }

[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E5%A0%86/10978086?fr=aladdin