文档介绍：数据结构排序实验报告《数据结构》课程设计报告实验五排序一、需求分析:本演示程序用C++,完成各种排序的实现,对输入的一组数字实现不同的排序方法,对其由小到大顺序输出。(1)分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。(2)、对存储的函数即输入的数字进行遍历。(3)、初始化函数对输入的数字进行保存。(4)、主函数实现使用者操作界面的编写,对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。(5)、程序所能达到的功能:完成对输入的数字的生成,并通过对各排序的选择实现数字从小到大的输出。二、程序主要功能以及基本要求:(1)、设计一个菜单,格式如下:1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出(2)、选择不同的菜单但进行相应的排序,并给出排序的关键字序列。三、系统框架图:本程序包含了9个函数,它们分别是:(1)、直接插入排序的算法函数InsertSort()。(2)、希尔排序的算法函数ShellSort()。主函数(3)、冒泡排序算法函数BubbleSort()。操作界面的设计,函数的调用。对输入的数组进行遍历初始化各个排序算法函数(4)、快速排序的算法函数Partition()。(5)、选择排序算法函数SelectSort()。(6)、堆排序算法函数HeapAdjust()。(7)、对存储数字的遍历函数Visit()。(8)、初始化函数InitSqList()。(9)、主函数main()。四、详细设计实现各个算法的主要内容,下面是各个函数的主要信息:(1)各个排序函数的算法:一、直接插入排序voidInsertSort(SqList&L){ inti,j; for(i=2;i<=;i++) { if([i].key<[i-1].key) { [0]=[i]; [i]=[i-1]; for(j=i-2;([0].key<[j].key);j--) [j+1]=[j]; [j+1]=[0]; } }}二、希尔排序voidShellSort(SqList&L){ inti,j;intdk=1;//增量 while(dk<=) dk=3*dk+1;//增大增量 while(dk>0) { dk/=3;//减小增量 for(i=dk;i<=;i++) { [0].key=[i].key; j=i; while((j>=dk)&&([j-dk].key>[0].key)) { [j].key=[j-dk].key; j-=dk; } [j].key=[0].key; } }}三、冒泡排序voidBubbleSort(SqList&L){ inti,j; for(i=0;i<;i++) { intflag=1; for(j=0;j<;j++) if([j].key>[j+1].key) { flag=0; inttemp; temp=[j].key; [j].key=[j+1].key; [j+1].key=temp; } //若无交换说明已经有序 if(flag==1) break; }}四、快速排序intPartition(SqList&L,intlow,inthigh){ //分割区域函数 [0]=[low]; intpivotkey=[low].key;//一般将顺序表第一个元素作为支点 while(low<high) { while(low<high&&[high].key>=pivotkey) high--; [low]=[high]; while(low<high&&[low].key<=pivotkey) low++; [high]=[low]; } [low]=[0];//返回枢轴位置 returnlow;}voidQSort(SqList&L,intlow,inthigh){ //每张子表的快速排序 if(low<high) { intpivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); }}voidQuickSort(SqList&L){ QSort(L,1,);}五、简单选择排序voidSelectSort(SqList&L){ intmin; intj; for(inti=0;i<;i++) { //选择第i小的记录,并交换 j=i; min=[i].key; for(intk=i;k<;k++) { //在R[i..n-1]中选择最小的记录 if([k].key<min) { min=[k].key; j=k; } } if(i!=j) { //与第i个记录交换 inttemp=[i].key; [i].key=[j