堆排序之大顶堆

╰半橙微兮° 2022-05-09 09:58 176阅读 0赞

对于具有n个元素的序列，采用堆积排序方法需要进行n-1趟排序才能达到目的

#include <stdio.h>
    void ADJUST(int a[],int i,int n){ 
     a[0] = a[i];
    	for (int j = 2*i;j<=n;j*=2) //层层向下遍历,找到比自己大的孩子节点,
    	//替换自己,最后把头结点也就是最大值,放到尾部a[i](数组末尾)
    	{
    		if (j<n && a[j]<a[j+1])
    		{
    			j++;
    		}
    		if (a[0]>a[j])
    		{
    			break;
    		}
    		a[i] = a[j];
    		i = j;
    	}
    	a[i] = a[0];
    }
    void HEAP_SORT(int a[],int n){
    	for (int i=n/2;i>=1;i--) //n/2表示叶子节点的父母节点的坐标,根节点为1
    	{
    		ADJUST(a,i,n);
    	}
    	for (i=1;i<n-1;i++)
    	{
    		printf("%2d ",a[i]);
    	}
    	printf("%2d\n",a[i]);
    	for (int j=n-1;j>=1;j--)
    	{
    		int temp = a[j+1];
    			a[j+1] = a[1];
    		a[1] = temp;
    		ADJUST(a,1,j); //交换堆积第一个元素与最后的那个元素的位置
    	}
    
    }
    int main(){
    	int a[] = {-1,26,5,77,1,61,11,59,15,48,19};  //a[0]为临时变量
    	int n = sizeof(a)/sizeof(int); //求出数组总长度
    	HEAP_SORT(a,n-1);  
    	printf("最终结果\n");
    	for (int i=1;i<n-1;i++)
    	{
    		printf("%2d ",a[i]);
    	}
    	printf("%2d\n",a[i]);
    
    }

运行结果  
![在这里插入图片描述][70]

小堆积代码只需更改  
void ADJUST(int a\[\],int i,int n)\{  
a\[0\] = a\[i\];  
for (int j = 2*i;j<=n;j*=2) //层层向下遍历,找到比自己大的孩子节点,替换自己,最后把头结点也就是最大值,放到尾部ai

if (j<n && a[j]>a[j+1]) //把大于号>改成小于号<
    		{
    			j++;
    		}
    		if (**a[0]<a[j]**)  //把大于号>改成小于号<
    		{
    			break;
    		}

运行效果如图  
![在这里插入图片描述][70 1]

[70]: /images/20220509/5a9611f6e0f541a09b4783a761a268e3.png
[70 1]: /images/20220509/ef8174f96bfb496e8e9490b9633e9527.png