快速排序与堆排序

一、实验目的1.掌握快速排序和堆排序的过程；2.熟悉快速排序和堆排序的算法。二．实验环境实验室网络环境,vc++6.0三、实验内容与步骤1.先根据自己的需求输入一个顺序表。2.通过利用快速排序法按非递减排序已有的顺序表。3.通过利用堆排序按非递减排序已有的顺序表。四、实验过程与分析#includestdio.htypedefstruct{intkey;}keytype;typedefstruct{keytyper[100];intlength;}sqlist;创建顺序表:voidcreat(sqlist*l){inti,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].key;while(lowhigh){while(lowhigh&&l-r[high].key=pivotkey)--high;l-r[low]=l-r[high];while(lowhigh&&l-r[low].key=pivotkey)++low;l-r[high]=l-r[low];}l-r[low]=l-r[0];returnlow;}快速排序:voidQsort(sqlist*l,intlow,inthigh){intpivotloc;if(lowhigh){pivotloc=partion(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(\n);for(i=1;i=2*l-length;i++)printf(--);printf(\n);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(jm&&h-r[j].keyh-r[j+1].key)++j;if(rc.key=h-r[j].key)break;h-r[s]=h-r[j];s=j;}h-r[s]=rc;}对顺序表h进行堆排序:voidheapsort(sqlist*h){keytyperc;inti;for(i=h-length/2;i0;--i)heapadjust(h,i,h-length);for(i=h-length;i1;--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(快速排序的结果是:\n);display(&t);printf(\n);heapsort(&t);printf(堆排序的结果是:\n);display(&t);}运行结果如下：