104-对堆排序算法的实现和分析

超、凢脫俗 2022-12-29 06:29 120阅读 0赞

## 堆排序算法 ##

首先先引入需要的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

堆排序算法需要用到**完全二叉树**  
**满二叉树**：深度为k的二叉树，他的节点个数为2^k-1  
**完全二叉树**： 从根节点开始，对节点个数为n的二叉树进行编号，深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**堆**：最大堆 – 每一棵子树，他的根节点比左右孩子都大  
最小堆 – 每一棵子树，他的根节点比左右孩子都小

***堆排序的思想***  
堆排序中的堆是一棵**完全二叉树**：  
如果当前的父节点下标为 i ， 则左孩子的下标 2*i+1,  
右孩子的下标 2*i+2  
如果一个孩子的下标是j，则其父节点的下标是 （j-1）/2

**堆排序过程**： 将待排序序列构建成一个大根堆  
整个调整是从最后一棵子树开始向上调整  
每次的调整过程都是从这个子树的根向下调整  
再执行排序过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70]  
接下来是对堆排序算法的实现

void OneAdjust(int *arr,int len,int root)//进行一次调整
    {
        
    	int i=root;
    	int tmp=arr[i];
    	int j=2*i+1;
    	while(j<len)
    	{
        
    		if(j+1<len&&arr[j+1]>arr[j]) j++;
    		if(arr[j]<tmp) break;
    		arr[i]=arr[j];
    		i=j;
    		j=2*i+1;
    	}
    	arr[i]=tmp;
    }
    
    void CreateHeap(int *arr,int len)//从最后一棵子树开始
    {
        
    	//最后一棵子树的根节点下标
    	int last_root=(len-2)/2;
    	for(int i=last_root;i>=0;--i)
    	{
        
    		OneAdjust(arr,len,i);
    	} 
    }
    
    void HeapSort(int *arr,int len)
    {
        
    	CreateHeap(arr,len);
    	for(int i=0;i<len-1;++i)
    	{
        
    		SwapValue(&arr[0],&arr[len-1-i]);
    		OneAdjust(arr,len-1-i,0);
    	}
    }

最后完成主函数

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

运行结果如下  
![在这里插入图片描述][20201220190038819.png_pic_center]  
***堆排序的分析***  
时间复杂度： O(nlogn)  
空间复杂度： O(1)  
稳定性： 不稳定（有跳跃数字）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/00783c8b7895474a91d0064d352e5df1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/49bd0d02b5654494ab95f25c11f23bdc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpbnpleXU2NjY_size_16_color_FFFFFF_t_70]: /images/20221120/e727dafc43544edfb38f8570df6d647b.png
[20201220190038819.png_pic_center]: /images/20221120/33e700b2ae3942c2a9bdbfca00aafb87.png