最小堆排序

算法设计与分析实验三

随机数的最小堆排序问题

（1）实验题目

随机数的最小堆排序问题（2）实验目的

掌握随机数的产生方式；掌握最小堆的建立和最小堆的排序问题。（3）调试通过并正确执行给定功能要求的实验代码

#include #include #include void main() {

void SORT(int n,int array[]);

void push_down(int first,int last,int A[]);

int a,b; FILE*fp;

if((fp=fopen("input.txt","r"))==NULL) { printf("cannot open this file/n"); exit(0); }

fscanf(fp,"%d,%d",&a,&b); fclose(fp);

srand((unsigned)time(NULL)); int c=b-a;

int i,j,m[21]={0};

for(i=1;i

void SORT(int n,int array[]) {

void push_down(int first,int last,int A[]); void swap(int *x,int *y);

FILE *fp1;

if((fp1=fopen("output.txt","w"))==NULL) { printf("cannot open this file\n");

exit(0); }

fputs("产生的20个随机数为：\n",fp1); printf("产生的20个随机数为：\n");

int k;

for(k=1;k

printf("\n"); printf("start:\n"); fputs("\n",fp1); fputs("start:\n",fp1);

int i;

printf("生成最小堆\n"); fputs("生成最小堆\n",fp1); for(i=n/2;i>=1;i--) { push_down(i,n,array); int j;

for(j=1;j

fprintf(fp1,"%d ",array[j]); }

printf("\n"); fputs("\n",fp1); }

printf("最小堆排序\n"); fputs("最小堆排序\n",fp1);

for(i=n;i>=2;i--) { swap(&array[1],&array[i]); push_down(1,i-1,array); int j; for(j=1;j

printf("%d ",array[j]); fprintf(fp1,"%d ",array[j]); } printf("\n"); fputs("\n",fp1); }

fclose(fp1); }

void push_down(int first,int last,int A[]) {

void swap(int *x,int *y); int r; r=first;

while(rA[2*r]) swap(&A[r],&A[2*r]); r=last; } else if(A[r]>A[2*r]&&A[2*r]A[2*r+1]&&A[2*r+1]

void swap(int *x,int *y) {

int temp1; temp1=*x; *x=*y; *y=temp1; }

（4）实验结果截图