排序算法之堆排序

短命女 2022-09-25 15:22 196阅读 0赞

同样的先上这张图

![Center][]

下面看一种较为复杂的选择排序 ——堆排序：

首先来看一下什么是堆，堆用一个一维的数组模拟二叉树的结构，即堆数组的第一个元素为第二、第三个元素的父结点，即第i(i从0开始)个元素是第2i+1和第2i+2个元素的父结点，由此我们可以得到每一个结点的父结点，设为j。由 n=2j+1（n为奇数）和 n=2j+2（n为偶数）得 j=(n-1)/2（是奇数）；j=(n-2)/2 （n是偶数）。

知道了堆的定义之后我们用堆来实现排序，首先我们构建一个小顶堆（父结点比子结点小），然后每次弹出根结点，重新调整堆，直到堆为空。

因此，实现堆排序需解决两个问题：  
1. 如何将n 个待排序的数建成堆；  
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

对于第一个问题，我们知道最后一个结点的父结点是floor( (n-1) / 2)，以只需要对以该结点为根结点的树进行筛选，使其成为小顶堆。之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

![1342596333_5296.jpg][]

对于第二个问题，调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

![1342595226_8095.jpg][]

C++代码

/*
    * 堆排序
    * 先建立一个小顶堆
    * 然后弹出堆顶元素，再调整堆为小顶堆
    * O(nlogn)
    * O(1)
    * 不稳定
    */
    template <typename T>
    void SortHelp<T>::heapSort(T l[], int length)
    {
    	//由n=2j+1或n=2j+2得，j=(n-1)/2,n是奇数；j=(n-2)/2,n是偶数。
    	//而n是偶数时，(n-1)/2 == (n-2)/2
    
    	//建立小顶堆(从大到小排序）
    	for (int i = length - 1; i > 0; i--)
    	{
    		if (l[i] < l[(i - 1) / 2])
    		{
    			l[i] += l[(i - 1) / 2];
    			l[(i - 1) / 2] = l[i] - l[(i - 1) / 2];
    			l[i] = l[i] - l[(i - 1) / 2];
    		}
    	}
    
    	//弹出堆顶元素放到最后
    	for (int i = length - 1; i > 0; i--)
    	{
    		//将堆顶元素与堆底元素交换
    		l[i] += l[0];
    		l[0] = l[i] - l[0];
    		l[i] = l[i] - l[0];
    		//调整堆
    		for (int j = i - 1; j > 0; j--)
    		{
    			if (l[j] < l[(j - 1) / 2])
    			{
    				l[j] += l[(j - 1) / 2];
    				l[(j - 1) / 2] = l[j] - l[(j - 1) / 2];
    				l[j] = l[j] - l[(j - 1) / 2];
    			}
    		}
    	}
    }

设树深度为k，![1342597015_2320.jpg][]。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

![1342597082_9043.jpg][]

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

由于不需要额外的辅助空间，其空间复杂度为O(1)，即常量复杂度。

由于堆在筛选过程中可能打乱顺序，所以堆排序不是稳定的。

[Center]: /images/20220717/dfaf0f8d3c37492195418662655f1f35.png
[1342596333_5296.jpg]: https://img-my.csdn.net/uploads/201207/18/1342596333_5296.jpg
[1342595226_8095.jpg]: https://img-my.csdn.net/uploads/201207/18/1342595226_8095.jpg
[1342597015_2320.jpg]: https://img-my.csdn.net/uploads/201207/18/1342597015_2320.jpg
[1342597082_9043.jpg]: https://img-my.csdn.net/uploads/201207/18/1342597082_9043.jpg