堆选择排序C/C++代码实现

蔚落 2023-02-23 12:29 23阅读 0赞

## 举例： ##

树形排序即简单选择排序的改进，第一躺比较后对记录大小进行记录，以后不再逐一比较，堆排序 (Heap Sort) 是一种树形选择排序。

堆实质上是满足如下性质的完全二叉树：树中所有非终端结点的值均不大于（或不小于） 其左、 右孩子结点的值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
步骤：  
1，按堆的定义将待排序序列r\[l…n\]调整为大根堆（这个过程称为建初堆），交换r\[l\]和r\[n\] , 则r\[n\]为关键字最大的记录。  
2，将r\[l . .n-1\]重新调整为堆，交换r\[I\]和r\[n-1\], 则r\[n-1\]为关键字次大的记录。 3，循环n-I次，直到交换了r\[I\]和r\[2\]为止，得到了一个非递减的有序序列r\[l…n\]。

## 算法属性： ##

时间复杂度为O(nlog2(n))。  
空间复杂度最坏情况为O(1)  
不稳定排序。  
只能用于顺序结构。  
初始建堆所需的比较次数较多，因此记录数较少时不宜采用。

## 代码实现： ##

而在完全二叉树中，所有序号大于(n/2)取下限的结点都是叶子。

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //堆选择排序(大顶堆)
    
    //调整堆（除根节点外其余左右子树均已是堆） 
    void HeapAdjust(SqList &L, int s, int m)	//r[s...m]
    {
        
    	RedType rc = L.r[s];				//其中r[s]为根
    	for (int j = s * 2; j <= m; j *= 2)		//根据完全二叉树结构
    	{
        
    		if (j< m && L.r[j].key < L.r[j + 1].key)
    		{
        
    			++j;						//直到j指向左右孩子中最大的结点
    		}
    		if (rc.key >= L.r[j].key)
    		{
        
    			break;						//如果根结点已经比左右孩子大了，则退出循环
    		}
    
    		L.r[s] = L.r[j];				//把最大的孩子结点赋值到根结点，并把s置为j进行下一轮循环
    		s = j;
    	}
    	L.r[s] = rc;						//此时的s为上面j赋值，把根结点插入
    
    }
    
    
    //建初堆（利用调整堆算法对每个非叶子结点逐个调整）
    void CreatHeap(SqList &L)
    {
        
    	int n = L.length;
    	// 根据完全二叉树中，所有序号大于n/2的结点都是叶子
    	//从n/2开始向前 逐个调用调整算法
    	for (int i = n / 2; i > 0; --i)
    	{
        
    		HeapAdjust(L, i, n);
    	}
    }
    
    //根据建初堆和调整算法实现推排序
    void HeapSort(SqList &L)
    {
        
    	RedType t;
    	CreatHeap(L);
    	for (int i = L.length; i>1; --i)			//将根结点和最后一个（未排序的）记录互换
    	{
        
    		t = L.r[1];
    		L.r[1] = L.r[i];
    		L.r[i] = t;
    		HeapAdjust(L, 1, i - 1);			//调用调整堆重新调整根结点
    	}
    }
    
    
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 49;
    	L.r[2].key = 38;
    	L.r[3].key = 65;
    	L.r[4].key = 97;
    	L.r[5].key = 76;
    	L.r[6].key = 13;
    	L.r[7].key = 27;
    	L.r[8].key = 49;
    	L.length = 8;
    
    	HeapSort(L);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707193441336.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707193833439.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70