排序之堆排序

我就是我 2022-04-22 09:22 219阅读 0赞

> # 堆排序简介 #

堆排序是利用数据结构堆的性质设计的一种排序算法，堆排序属于选择排序，这种排序是不稳定的。在任何情况下，堆排序的时间复杂度都是O(nlogn)。

> ## 堆介绍 ##

堆是计算机科学中的一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。(百度百科)

堆的性质:

堆具有完全二叉树的所有性质，并且堆的根节点的值全部大于或者全部小于子节点的值。如图所示

用数组表示大顶堆与小顶堆的定义就是:

**大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]**

**小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]**

![1024555-20161217182750011-675658660.png][]

> # 堆排序的基本思想 #

将待排序数列构造成一个大顶堆，然后将最顶端与最末端进行交换，此时末端就是最大值，再将此数列余下n-1个数构造成一个大顶堆，如此反复，直至排序结束。

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    void printArray(int a[],int N)
    {
    	for(int i = 0; i < N; i++)
    		cout << a[i] << " ";
    			
    	cout << endl;
    } 
    
    void max_heapify(int a[],int start,int end)
    {	
    	int dad = start;            //父节点
    	int son = dad * 2 + 1;      //子节点  
    	while( son <= end)          //比较并交换，再将子节点与孙子节点比较
    	{
    		if(son+1 <= end && a[son] < a[son + 1])
    			son++;
    		if(a[dad] > a[son])
    			return;
    		else
    		{
    			swap(a[son],a[dad]);
    			dad = son;
    			son = son * 2 + 1;
    		}
    	}
    }
    
    void HeapSort(int a[],int N)
    {
    	for(int i = N / 2 - 1; i >= 0; i--)        //生成大顶堆
    	{
    		max_heapify(a,i,N-1);              
    	} 
    	for(int i = N - 1; i >= 0; i--)            
    	{
    		swap(a[0],a[i]);               //交换0(最大数)位置和i位置的数
    		max_heapify(a,0,i-1);          //交换后需要继续调整成大顶堆
    	}
    }
    
    int main()
    {
    	srand((unsigned)time(NULL));  //定义随机数种子
    	int N;
    	while(cin >> N)               //设置N个随机数
    	{
    		int a[N];
    		for(int i = 0; i < N; i++)
    		{
    			a[i] = rand() % 65536;
    		}
            printArray(a, N);      //打印排序前数组
    		HeapSort(a, N);        //进行堆排序
    		printArray(a, N);      //打印排序后数组
    	}
    	
    	return 0;
    }

[1024555-20161217182750011-675658660.png]: /images/20220422/b58b923b88e24f118cf8139414fe3763.png