快速排序与堆排序.doc

《快速排序与堆排序.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、实验目的1.掌握快速排序和堆排序的过程；2.熟悉快速排序和堆排序的算法。二．实验环境实验室网络环境,vc++6.0三、实验内容与步骤1.先根据自己的需求输入一个顺序表。2.通过利用快速排序法按非递减排序已有的顺序表。3.通过利用堆排序按非递减排序已有的顺序表。四、实验过程与分析#includetypedefstruct{intkey;}keytype;typedefstruct{keytyper[100];intlength;}sqlist;创建顺序表:voidcreat(sqlist*l){inti,

2、key;printf("请输入该顺序表的长度:");scanf("%d",&l->length);printf("请输入数字",l->length);for(i=1;i<=l->length;i++){scanf("%d",&key);l->r[i].key=key;}}交换顺序表中子表r[low...high]的记录，使枢轴记录到位，并返回其所在的位置:intpartion(sqlist*l,intlow,inthigh){intpivotkey;l->r[0]=l->r[low];pivotkey=l->r[low].k

3、ey;while(lowr[high].key>=pivotkey)--high;l->r[low]=l->r[high];while(lowr[low].key<=pivotkey)++low;l->r[high]=l->r[low];}l->r[low]=l->r[0];returnlow;}快速排序:voidQsort(sqlist*l,intlow,inthigh){intpivotloc;if(low

4、n(l,low,high);//对l.r[low..high]进行一次划分Qsort(l,low,pivotloc-1);//对低子序列递归排序，pivotloc是枢轴位置Qsort(l,pivotloc+1,high);//对高子序列递归排序}}显示顺序表:voiddisplay(sqlist*l){inti;for(i=1;i<=l->length;i++)printf("%-4.2d",i);printf("");for(i=1;i<=2*l->length;i++)printf("--");printf(""

5、);for(i=1;i<=l->length;i++)printf("%-4.2d",l->r[i].key);}调整h->r[s]的关键字，使h->r[s]成为一个大顶堆:voidheapadjust(sqlist*h,ints,intm){keytyperc;intj;rc=h->r[s];for(j=2*s;j<=m;j*=2){if(jr[j].keyr[j+1].key)++j;if(rc.key>=h->r[j].key)break;h->r[s]=h->r[j];s=j;}h->r[s]=

6、rc;}对顺序表h进行堆排序:voidheapsort(sqlist*h){keytyperc;inti;for(i=h->length/2;i>0;--i)heapadjust(h,i,h->length);for(i=h->length;i>1;--i){rc=h->r[1];h->r[1]=h->r[i];h->r[i]=rc;heapadjust(h,1,i-1);}}主函数:voidmain(){sqlistt;inti;creat(&t);Qsort(&t,1,t.length);printf("快速排序的结果是

7、:");display(&t);printf("");heapsort(&t);printf("堆排序的结果是:");display(&t);}运行结果如下：