堆排序算法流程图(堆排序算法)

导读 大家好,我是小典,我来为大家解答以上问题。堆排序算法流程图,堆排序算法很多人还不知道,现在让我们一起来看看吧!#include<stdio.h>#in...

大家好,我是小典,我来为大家解答以上问题。堆排序算法流程图,堆排序算法很多人还不知道,现在让我们一起来看看吧!

#include<stdio.h>

#include<malloc.h>

#include<time.h>

#define LISTSIZE 100

#define MORESIZE 100

#define overflow -1

typedef struct

{

int data;

int fre;

}Cell;

typedef struct {

Cell *elem;

long int length;

unsigned long int count1;

unsigned long int count2;

long int listsize;

}SqList;

SqList L1;

clock_t start,end;

FILE *p,*w;

int main (void)

{

void assign(Cell *a,Cell *b);

int LT(int a,int b);

void HeapSort (SqList &H);

void HeapAdjust (SqList &H,int s , int m);

void exchange(Cell *a,Cell *b);

//读入

int time=0;

while(time<4)

{

switch (time)

{

case 0:

p=fopen("data01.txt","r");

w=fopen("sorted01.txt","w");

break;

case 1:

p=fopen("data02.txt","r");

w=fopen("sorted02.txt","w");

break;

case 2:

p=fopen("data03.txt","r");

w=fopen("sorted03.txt","w");

break;

case 3:

p=fopen("data04.txt","r");

w=fopen("sorted04.txt","w");

break;

}

L1.count1=0;

L1.count2=0;

time++;

L1.elem=(Cell *)malloc((LISTSIZE+1)*sizeof(Cell));

L1.listsize=LISTSIZE;

L1.length=1;

Cell *newbase;

while(!feof(p))

{

if (L1.length>L1.listsize){

newbase=(Cell *)realloc(L1.elem,(L1.listsize+MORESIZE+1)*sizeof(Cell));

if (!newbase)

return overflow;

L1.elem=newbase;

L1.listsize+=MORESIZE;}

fscanf (p,"%d (%d) ",&((L1.elem+L1.length)->data),&((L1.elem+L1.length)->fre));

L1.length++;

}

L1.length--;

printf ("listsize=%d length=%d ",L1.listsize,L1.length);

//排序

start=clock();//开始计时

HeapSort(L1); //堆排序

end=clock(); //结束计时

printf ("Time: %lf ",(double)(end-start)/CLOCKS_PER_SEC);//输出时间

for (int i=1;i<L1.length+1;++i)

fprintf (w,"%d (%d) ",(L1.elem+i)->data,(L1.elem+i)->fre);

fprintf (w,"比较次数%u,移动次数%u ",L1.count1,L1.count2);

printf ("比较次数%u,移动次数%u ",L1.count1,L1.count2);

fprintf (w,"Copyright Reserved,Cheng Xuntao,NWPU");

fclose(p);

fclose(w);

}

return 0;

}

int LT(int a,int b)//比较函数

{L1.count1++;<br/> if (a<b){<br/> <br/> return 1;}

else return 0;

}

void assign(Cell *a,Cell *b)//赋值函数

{

a->data=b->data;

a->fre=b->fre;

L1.count2++;

}

void exchange(Cell *a,Cell *b)//交换记录

{

int temp;

temp=a->data;

a->data=b->data;

b->data=temp;

temp=a->fre;

a->fre=b->fre;

b->fre=temp;

L1.count2+=3; //+=3

}

void HeapAdjust (SqList &H,int s , int m)//调节其成为堆

{

Cell *rc;

rc=(Cell *)malloc(sizeof(Cell));

int j;

assign(rc,H.elem+s); //暂存

for (j=2*s;j<=m;j*=2){ //沿值较大的孩子节点向下筛选

if (j<m && LT((H.elem+j)->data,(H.elem+j+1)->data ))

j++; //j为值较大的记录的下标

if (!LT(rc->data,(H.elem+j)->data))

break; //rc应插入在位置s上

assign((H.elem+s),(H.elem+j));

s=j;

}

assign((H.elem+s),rc); //插入

}//HeapAdjust

void HeapSort (SqList &H) //堆排序

{

int i;

for (i=H.length/2;i>0;--i) //把L.elem[1...H.length]建成堆

HeapAdjust(H,i,H.length);

for (i=H.length;i>1;--i)

{

exchange(H.elem+1,H.elem+i); //将堆顶记录和当前未经排序的子序列L.elem[i...i]中最后一个记录相互交换

HeapAdjust(H,1,i-1); //重新调整其为堆

}

}//HeapSort

本文到此讲解完毕了,希望对大家有帮助。

最新文章