复习数据结构：排序算法（六）——堆排序

淡淡的烟草味﹌ 2022-08-07 01:56 180阅读 0赞

对于堆排序，前面一篇博文中已经复习到了堆排序，这里就简单介绍一下，并给出核心部分的解释。

堆排序是一种不稳定的排序，也是内排序。

时间复杂度为O(nlogn)。

以最大堆为例，堆排序的基本思想是：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；  
  
2)将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R\[1,2...n-1\]<=R\[n\];  
  
3)由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

其实，堆排序最重要的两部分就是：初始化堆和调整堆。

代码如下：

#include<iostream>
    #include<algorithm>
    using namespace std; 
    
    // 调整堆函数
    void HeapAdjust(int *a, int i, int size)  // a：数组；i：节点index；size：树的规模
    {
    	int lchild = 2 * i;   // 节点的左孩子编号
    	int rchild = 2 * i + 1;   // 节点的右孩子编号
    	int max = i;  //节点编号备份
    	if(i <= size/2 - 1)
    	{
    		if(lchild <= size && a[lchild] > a[max])  // 左孩子比节点值要大
    			max = lchild; 
    		if(rchild <= size && a[rchild] > a[max])  // 右孩子比节点值要大
    			max = rchild; 
    		if(max != i)  // 如果上面发生了交换，也就是如果上面有if成立了
    		{
    			swap(a[i], a[max]);   // 首先要交换二者的真实值，因为上面只是index的交换
    			HeapAdjust(a, max, size);  // 其次，需要判断交换之后还需要重新调整吗
    		}
    	}
    }
    
    //建立堆函数
    void BuildHeap(int *a, int size)  
    {
    	int i; 
    	for(i = size/2 - 1; i >= 0; i--)  // 非叶子节点最大序号值为size/2，需要遍历所有的节点
    	{
    		HeapAdjust(a, i, size);   // 调整
    	}
    }
    
    // 堆排序函数
    void HeapSort(int *a, int size)
    {
    	int i; 
    	BuildHeap(a, size); 
    	for(i = size; i >= 0; i--)
    	{
    		swap(a[0], a[i]);  //  交换堆顶和最后一个元素，每次将剩余元素中的最大者放到最后面
    		HeapAdjust(a, 0, i-1);  // 重新调整堆顶节点成为大顶堆，这个时候就要除出最后一个元素，范围是1~n-1
    	}
    }
    
    int main()
    {
    	int a[] = {100, 16, 20, 3, 11, 17, 8};
    	int size = 7; 
    	HeapSort(a, size); 
    	for(int i = 0; i < size; i++)
    	{
    		cout<<a[i]<<endl; 
    	}
    	cout<<endl; 
    
    	return 0; 
    }

参考链接：

http://blog.csdn.net/puqutogether/article/details/43195703

http://blog.csdn.net/hguisu/article/details/7776068

http://blog.csdn.net/xiazdong/article/details/8462393

http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html