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

《数据结构实验七(排序算法的实现)题目和源程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验7：至少三种排序算法的程序实现（第十六周星期三7、8节）一、实验目的1．掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。2．对各种查找、排序技术的时间、空间复杂性有进一步认识。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容编写程序实现下述五种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，491．简单插入排序2．冒泡排序3．快速排序4．归并排序5．堆排序四、思考与提高1．设有1000个无序的元素，希望用最快的速度挑出其中前1

2、0个最大的元素，采用哪一种排序方法最好？为什么？2．如何构造一种排序方法，使五个整数至多用七次比较就可以完成排序任务？/*----------------------------------------*07_排序.cpp--排序的相关操作*对排序的每个基本操作都用单独的函数来实现*水上飘2009年写----------------------------------------*///ds07.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include#includeusingnamespacestd;

3、#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];//将其暂存到

4、arr[0]intlow=1;inthigh=i-1;while(low<=high){//在arr[low...high]中折半查找有序插入的位置intm=(low+high)/2;//折半if(L.arr[0].key=high+1;j--)L.arr[j+1]=L.arr[j];//记录后移L.arr[high+1]=L.arr[0];//插入}//for}//BInsertSort//直接插入排序voidinsertS

5、ort(SqList&L){for(inti=2;i<=L.length;i++){if(L.arr[i].key

6、ist&L){RedType*temp=NULL;for(inti=1;iL.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(SqL

7、ist&L,intlow,inthigh){L.arr[0]=L.arr[low];//子表的第一个记录做枢轴记录KeyTypepivotKey=L.arr[low].key;//枢轴记录关键字while(low=pivotKey){high--;}//whileL.arr[low]=L.arr[high];//将比枢轴小的记录移到低端while(low