数据结构实验七(排序算法的实现)题目和源程序

实验7：至少三种排序算法的程序实现（第十六周星期三7、8节）一、实验目的1．掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。2．对各种查找、排序技术的时间、空间复杂性有进一步认识。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容编写程序实现下述五种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，491．简单插入排序2．冒泡排序3．快速排序4．归并排序5．堆排序四、思考与提高1．设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，采用哪一种排序方法最好？为什么？2．如何构造一种排序方法，使五个整数至多用七次比较就可以完成排序任务？/*----------------------------------------*07_排序.cpp--排序的相关操作*对排序的每个基本操作都用单独的函数来实现*水上飘2009年写----------------------------------------*///ds07.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includeiostream#includeiomanipusingnamespacestd;#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;//关键字项KeyTypedata;//数据项}RedType;//记录类型typedefstruct{RedTypearr[MAXSIZE+1];//arr[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型typedefSqListHeapType;//折半插入排序voidbInsertSort(SqList&L){for(inti=2;i=L.length;i++){L.arr[0]=L.arr[i];//将其暂存到arr[0]intlow=1;inthigh=i-1;while(low=high){//在arr[low...high]中折半查找有序插入的位置intm=(low+high)/2;//折半if(L.arr[0].keyL.arr[m].key)high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区}//whilefor(intj=i-1;j=high+1;j--)L.arr[j+1]=L.arr[j];//记录后移L.arr[high+1]=L.arr[0];//插入}//for}//BInsertSort//直接插入排序voidinsertSort(SqList&L){for(inti=2;i=L.length;i++){if(L.arr[i].keyL.arr[i-1].key){//if,需将L.arr[i]插入有序子表L.arr[0]=L.arr[i];//复制为哨兵L.arr[i]=L.arr[i-1];intj;for(j=i-2;L.arr[0].keyL.arr[j].key;j--)L.arr[j+1]=L.arr[j];//记录后移L.arr[j+1]=L.arr[0];//插入到正确位置}//if}//for}//InsertSort//冒泡排序voidbubbleSort(SqList&L){RedType*temp=NULL;for(inti=1;iL.length;i++){//第i趟排序for(intj=1;j=L.length-i;j++){//第j次排序if(L.arr[j].keyL.arr[j+1].key){//交换前后的位置L.arr[0]=L.arr[j];L.arr[j]=L.arr[j+1];L.arr[j+1]=L.arr[0];}//if}//forj}//fori}//bubbleSort/*交换顺序表中子表L.arr[low...high]的记录,枢轴记录到位,并返回其所在位置*/intpartition(SqList&L,intlow,inthigh){L.arr[0]=L.arr[low];//子表的第一个记录做枢轴记录KeyTypepivotKey=L.arr[low].key;//枢轴记录关键字while(lowhigh){//从表的两端交替向中间扫描while(lowhigh&&L.arr[high].key=pivotKey){high--;}//whileL.arr[low]=L.arr[high];//将比枢轴小的记录移到低端while(lowhigh&&L.arr[low].key=pivotKey){low++;}//whileL.arr[high]=L.arr[low];//将比枢轴大的记录移到高端}//whileL.arr[low]=L.arr[0];//枢轴记录到位returnlow;//返回枢轴位置}//paitition//对顺序表L中的子序列L.arr[low...high]做快速排序voidqSort(SqList&L,intlow,inthigh){if(lowhigh){//长度大于1KeyTypepivotLoc=partition(L,low,high);//将L.arr[low...high]一分为二qSort(L,low,pivotLoc-1);//对低子表递归排序，pivotLoc是枢轴位置qSort(L,pivotLoc+1,high);//对高子表递归排序}//if}//qSort//对顺序表L做快速排序voidquickSort(SqList&L){qSort(L,1,L.length);}//quickSort/*调整H.arr[s]的关键字，使H.arr[s...m]成为一个大顶堆（对其中记录的关键字而言）*/voidheapAdjust(HeapType&H,ints,intm){RedTyperc=H.arr[s];for(intj=2*s;j=m;j=j*2){//沿key较大的孩子结点向下筛选if(jm&&H.arr[j].keyH.arr[j+1].key){j++;//j为key叫大记录的下标}//ifif(!(rc.keyH.arr[j].key)){break;//rc应插入在位置s上}//ifH.arr[s]=H.arr[j];s=j;}//forH.arr[s]=rc;//插入}//heapAdjust//对顺序表H进行堆排序voidheapSort(HeapType&H){for(inti=H.length/2;i0;i--){//把H.arr[1...H.length]建成大顶堆heapAdjust(H,i,H.length);}//forfor(inti=H.length;i1;i--){//将堆记录当前未经排序的子序列H.arr[1...i]中的最后一个记录交换H.arr[0]=H.arr[1];H.arr[1]=H.arr[i];H.arr[i]=H.arr[0];heapAdjust(H,1,i-1);//将H.arr[1...i-1]重新调整为大顶堆}//for}//heapSort//初始化顺序表，给其赋值voidsetValue(SqList&L){KeyTypedata[8]={49,38,65,97,76,13,27,49};intn=8;L.arr[0].data=0;L.length=n;for(inti=1;i=L.length;i++){L.arr[i].data=data[i-1];L.arr[i].key=L.arr[i].data;}//for}//setValue//输出顺序表voidshow(SqList&L){for(inti=1;i=L.length;i++){if(i%5==0)coutendl;coutsetw(5)L.arr[i].data;}coutendl;}//show//调用排序函数进行排序voidperformance(SqList&L){cout原始序列：endl;show(L);SqListLI=L;insertSort(LI);cout直接插入排序结果：endl;show(LI);SqListLB=L;bInsertSort(LB);cout折半插入排序结果：endl;show(LB);SqListLBB=L;bubbleSort(LBB);cout冒泡排序结果：endl;show(LBB);SqListLQ=L;cout快速排序结果：endl;quickSort(LQ);show(LQ);HeapTypeH=L;cout堆排序结果：endl;heapSort(H);show(H);}//performanceint_tmain(intargc,_TCHAR*argv[]){SqListL;setValue(L);performance(L);cin.get();return0;}