计算机C语言的堆排序原理,最好是一个排序的例子,举数据进行现场排序

发布网友 发布时间：2022-04-30 16:13

我来回答

共2个回答

热心网友 时间：2022-06-27 04:46

#include<stdio.h>
#define N 6
int j,k;
//建堆函数
void build(int *a,int i,int n){
int tmp;
k=i;
j=2*k+1;
while(j<=n){
if((j<n)&&a[j]<a[j+1])
j++;
if(a[k]>=a[j])
break;
tmp=a[k];
a[k]=a[j];
a[j]=tmp;
k=j;
j=2*j+1;
}
}
//打印数组元素
void prnt(int *a,int n){
int i;
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
//打印堆函数
void prnthp(int *a,int b1,int b2){
int size;
int h=0,sum=0,item=1;
int i,j,cnt,start,tmp;
size=b2-b1+1;
while(sum<=size){
sum+=item;
h++;
item*=2;
}
item=1;
cnt=0;
start=b1;
tmp=1;
printf("\n========================================\n");
printf(" 堆：\n");
while(1){
for(i=0;i<h;i++){
for(j=0;j<h-i;j++)
printf(" ");
/*for(j=0;j<i+1;j++)
printf(" ");*/
for(j=0;j<tmp;j++){
if(cnt>size-1)
goto end;
printf("%4d",a[cnt++]);
}
printf("\n");
tmp*=2;
}
}
end:
printf("\n");
}
//打印排序好地数组
void prntar(int *a,int b2,int len){
int i;
printf(" 已排序： \n");
for(i=0;i<b2;i++)
printf(" ");
for(i=b2;i<=len;i++)
printf("%d ",a[i]);
printf("\n");
}
int main(){
int a[50];
int i;
int tmp;
int sum;
int len;
printf(" 堆排序\n");
printf("\n=============================================\n");
printf("\n请输入堆排序的数组元素个数，回车结束:\n");
scanf("%d",&len);
printf("\n请输入待排序的数组以回车结束：\n");
for(i=0;i<len;i++)
scanf("%d",&a[i]);
tmp=1;sum=0;
while (sum+tmp<=len){
sum+=tmp;
tmp*=2;
}
printf("\n==============================================================\n");
printf("\n 初始数组：\n");
prnt(a,len);
for(i=sum-1;i>=0;i--)
build(a,i,len-1);
prnthp(a,0,len-1);
for(i=0;i<len-1;i++){
tmp=a[0];
a[0]=a[len-1-i];
a[len-1-i]=tmp;
build(a,0,len-2-i);
prnthp(a,0,len-2-i);
prntar(a,len-1-i,len-1);
}
printf("\n===================================\n");
printf("\n 排序结果：\n");
prnt(a,len);
printf("\n=======================================\n");
return 0;
}

热心网友 时间：2022-06-27 04:46

#include <stdio.h>
void swap(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void maxHeapify(int* a, int i, int n)
{
int l, r, m;
do{
r = (i+1) << 1;
l = r - 1;
m = l < n && a[l] > a[i] ? l : i;
m = r < n && a[r] > a[m] ? r : m;
if(i != m) swap(a+i, a+m), i = m;
else break;
}while(1);
}
void heapSort(int* a, int n){
int i;
for(i = (n-1)/2; i >= 0; --i)
maxHeapify(a, i, n);
for(i = n-1; i > 0; --i)
{
swap(a, a+i);
maxHeapify(a, 0, --n);
}
}
void print(int* a, int* b)
{
while(a < b)
printf("%d ", *a++);
putchar('\n');
}
int main(){
int a[10] = {6,3,1,9,7,4,0,5,8,2};
heapSort(a, 10);
print(a, a+10);
return 0;
}