堆排序----(排序算法六)

1.算法原理

2.算法实现

#include <stdio.h>


//printArray打印出数组
void printArray(int a[],int size){  
    printf("数组为：[%d] ",a[0]);  
    for (int i=1;i<size;i++)  
    {  
        printf(" %x ",a[i]);  
    }  
    printf("
");  
}

//堆调整
void HeapAdjust(int a[],int s,int m){
	int temp=a[s];
	for(int j=2*s;j<=m;j*=2){
		if(j<m && a[j]<a[j+1]){
			++j;
		}
		if (!(temp<a[j]))
		{
			break;
		}
		a[s]=a[j];
		s=j;
	}
	a[s]=temp;
}


void main()
{
	//a[0]为监视哨
	int a[9]={0,0x49,0x38,0x65,0x97,0x76,0x13,0x27,0x49}; 
	int n=8;
	printArray(a,9);
	//建堆
	for (int i=n/2;i>0;--i)
	{
		HeapAdjust(a,i,n);
	}
	printArray(a,9);
	//输出堆
	for (int j=n;j>1;--j)
	{

		a[0]=a[1];
		a[1]=a[j];
		a[j]=a[0];
		HeapAdjust(a,1,j-1);
	}
	printArray(a,9);
}

3.结果

数组为：[0]  49  38  65  97  76  13  27  49
数组为：[0]  97  76  65  49  49  13  27  38
数组为：[39]  13  27  38  49  49  65  76  97