数据结构堆排序（Heap Sort）详解附C++代码实现：

谁借莪１个温暖的怀抱￠ 2024-02-19 18:13 51阅读 0赞

**目录**

简介：

算法描述：

代码实现：

总结：

--------------------

## 简介： ##

堆排序是利用堆这种数据结构所设计的排序算法，是一种近似于完全二叉树。分为大顶堆和小顶堆。时间复杂度为：o(nlog2(n)),不稳定。

## 算法描述： ##

知识储备：一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 \* i + 1和2 \* i + 2。如第0个结点左右子结点下标分别为1和2。

堆排序分为堆的插入和堆的删除

以小顶堆为例：

堆的插入：

![0_131415207877s7.gif][]

//  新加入i结点  其父结点为(i - 1) / 2
    void MinHeapFixup(int a[], int i)
    {
        int j, temp;
    	
    	temp = a[i];
    	j = (i - 1) / 2;      //父结点
    	while (j >= 0 && i != 0)
    	{
    		if (a[j] <= temp)
    			break;
    		
    		a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点
    		i = j;
    		j = (i - 1) / 2;
    	}
    	a[i] = temp;
    }

将数组中的每一个数都插入堆中：

void MinHeapSortInsert(int a[],int n)
    {
    	for(int i=1;i<n;i++)
    	MinHeapSortUp(a,i);
    }

堆的删除：

堆只能删除根节点，在数组中也就是0号元素。在堆排序中，将堆的最后一个节点与根节点交换，然后再从根节点到叶子节点进行一次自上到下的调整，使之满足最小堆的性质，首先找出左右孩子中最小的那个，与根节点比较，若小于最小的那个孩子节点，则不用调整；否则，进行向下调整。堆的删除相当于下沉过程。

void MinHeapSortDown(int a[],int i,int n)
    {
    	int temp=a[i];
    	int j=2*i+1;
    	while(j<n)
    	{
    		if(j+1<n&&a[j]>a[j+1])
    		j++;
    		if(temp<=a[j])
    		break;
    		a[i]=a[j];
    		i=j;
    		j=2*i+1;
    	}
    	a[i]=temp;
    }

堆排序通过堆的建立，再经过删除，每次删除都是将一个最值放到数组中（此时已经不在堆里），直到堆中没有任何数。

小顶堆通过堆排序得到从大到小的数组。

大顶堆得到从小到大的数组。

## 代码实现： ##

#include<iostream>
    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    using namespace std;
    #define range 10000
    void MinHeapSortUp(int a[],int i)
    {
    	int temp,j;
    	temp=a[i];
    	j=(i-1)/2;
    	while(j>=0&&i!=0)
    	{
    		if(a[j]<=temp)
    		break;
    		a[i]=a[j];
    		i=j;
    		j=(i-1)/2;
    		
    	}
    	a[i]=temp;
    }
    void MinHeapSortDown(int a[],int i,int n)
    {
    	int temp=a[i];
    	int j=2*i+1;
    	while(j<n)
    	{
    		if(j+1<n&&a[j]>a[j+1])
    		j++;
    		if(temp<=a[j])
    		break;
    		a[i]=a[j];
    		i=j;
    		j=2*i+1;
    	}
    	a[i]=temp;
    }
    void MinHeapSortInsert(int a[],int n)
    {
    	for(int i=1;i<n;i++)
    	MinHeapSortUp(a,i);
    }
    void MinHeapSortDelete(int a[],int n)
    {
    	int temp;
    	for(int i=n-1;i>=0;i--)
    	{
    		temp=a[0];
    		a[0]=a[i];
    		a[i]=temp;
    		MinHeapSortDown(a,0,i-1);
    	}
    }
    
    void MinHeapSort(int a[],int len)
    {
    	MinHeapSortInsert(a,len);
    	MinHeapSortDelete(a,len);
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	freopen("out_arr.txt","r",stdin);
    	freopen("out堆排序.txt","w",stdout);
    	int a[range];
    	int len=range;
    	for(int i=0;i<range;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	MinHeapSort(a,len);
    	for(int i=0;i<range;i++)
    	{
    		printf("%5d ",a[i]);
    		if((i+1)%50==0)
    		printf("\n");
    	}
    	end=clock();
    	printf("堆排序耗时：%dms\n",(float)(end-start)*1000.0/CLOCKS_PER_SEC); 
    	return 0;
    }

测试结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

## 总结： ##

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N \* logN)。故堆排序的时间复杂度为O(N \* logN)。是不稳定的排序算法。

小伙伴们，如果还看不懂，在评论区留言，乐意解答

[0_131415207877s7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1ae266496a0c4f4e8acce31fb8a4d2c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/62f29c63a1764a65af5decac3b0b063c.png