几种基本排序算法的实现

编辑版word数据结构实验报告实验题目：几种基本排序算法的实现姓名：张耀班级：计嵌151学号：1513052017编辑版word一、实验目的实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用内部排序算法，比较各算法的比较次数和移动次数。二、数据结构设计(1)设计待排序记录的存储结构。(2)设计待排序数据的存储结构。(3)输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。(4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移动次数。三、算法设计与N-S图算法设计：编写一个主函数main()，在主函数中设计一个简单的菜单，分别调用6种内部排序算法。为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数；设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程编辑版word序生成数据，以便随时更换排序数据，并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。四、程序清单#includeiostreamusingnamespacestd;voidshowMenu(){cout*菜单*endl;cout1.直接插入排序endl;cout2.冒泡排序endl;cout3.简单选择排序endl;cout4.快速排序endl;cout5.希尔排序endl;cout6.堆排序endl;cout7.退出程序endl;}structSqList{int*key;编辑版wordintlength;};voidCreateSqList(SqList&sl)//type为int{intn;cout建立顺序表endl请输入顺序表的长度endl;cinn;sl.length=n;sl.key=newint[sl.length+1];cout请输入数据：endl;for(inti=1;i=sl.length;i++){cinsl.key[i];}}voidCopy(SqList&L1,SqList&L2){L2.length=L1.length;L2.key=newint[L1.length+1];for(inti=1;i=L1.length;i++){编辑版wordL2.key[i]=L1.key[i];}}voidOutPut(SqList&L){for(intj=1;j=L.length;++j)coutL.key[j]\t;coutendl;}voidInsertSort(SqList&L){//对顺序表L作直接插入排序intk=0;intcompare_Time,move_Time;compare_Time=move_Time=0;for(inti=2;i=L.length;i++){if(L.key[i]=L.key[i-1])//需将L.key[i]插入有序子表{L.key[0]=L.key[i];//复制为哨兵L.key[i]=L.key[i-1];intj;编辑版wordfor(j=i-2;L.key[0]=L.key[j];--j){compare_Time++;L.key[j+1]=L.key[j];//记录后移move_Time++;}L.key[j+1]=L.key[0];//插入到正确位置k++;cout第k趟排序结果：;OutPut(L);}compare_Time++;}cout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}voidBubbleSort(SqList&L){intk=0;intcompare_Time,move_Time;compare_Time=move_Time=0;for(inti=1;iL.length;i++)//用i控制比较趟数共n-1趟{编辑版wordintt;for(intj=1;j=L.length-i;j++){compare_Time++;if(L.key[j]L.key[j+1]){t=L.key[j];L.key[j]=L.key[j+1];L.key[j+1]=t;move_Time++;}}k++;cout第k趟排序结果：;OutPut(L);}cout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}intSelectMinKey(SqList&L,intn,int&compare_Time){intmin=n;编辑版wordintminkey;//最小值minkey=L.key[n];for(inti=n+1;i=L.length;i++){if(L.key[i]minkey){minkey=L.key[i];min=i;}compare_Time++;}returnmin;}voidSelectSort(SqList&L){//对顺序表L作简单选择排序intj;intt;intk=0;intmove_Time=0,compare_Time=0;编辑版wordfor(inti=1;i=L.length;i++){j=SelectMinKey(L,i,compare_Time);//在L.key[i]--L.key[L.length]中选择最小的记录并将其地址赋给jif(i!=j)//交换记录{t=L.key[i];L.key[i]=L.key[j];L.key[j]=t;move_Time++;}compare_Time++;k++;cout第k趟排序结果：;OutPut(L);}cout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}intPartition(SqList&L,intlow,inthigh,int&compare_Time,int&move_Time){//交换顺序表L中子表key[low]--key[high]中的记录，枢轴记录到位，并返回其所在位置，//此时在它之前（后）的记录均不大（小）于它编辑版wordintpivotkey;L.key[0]=L.key[low];//用子表的第一个记录作枢轴记录pivotkey=L.key[low];//关键字while(lowhigh)//从表的两端交替向中间扫描{compare_Time++;while(lowhigh&&L.key[high]=pivotkey)--high;L.key[low]=L.key[high];move_Time++;//将比枢轴小的记录移至低端while(lowhigh&&L.key[low]=pivotkey)++low;L.key[high]=L.key[low];//将比枢轴大的记录移至高端move_Time++;}L.key[low]=L.key[0];//枢轴记录到位returnlow;//返回枢轴位置}voidQSort(SqList&L,intlow,inthigh,int&k,int&compare_Time,int&move_Time){intmid;//接收枢轴位置if(lowhigh){编辑版wordmid=Partition(L,low,high,compare_Time,move_Time);k++;cout第k趟排序结果：;OutPut(L);QSort(L,low,mid-1,k,compare_Time,move_Time);//对低子表进行排序QSort(L,mid+1,high,k,compare_Time,move_Time);//对高子表进行排序}}voidQuitSort(SqList&L)//对顺序表进行快速排序{intk=0;intcompare_Time=0,move_Time=0;QSort(L,1,L.length,k,compare_Time,move_Time);cout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}voidShellInsert(SqList&L,intdk,int&compare_Time,int&move_Time){//对顺序表进行一趟希尔插入排序for(inti=dk+1;i=L.length;i++)if(L.key[i]=L.key[i-dk])编辑版word{compare_Time++;L.key[0]=L.key[i];intj;for(j=i-dk;j0&&L.key[0]=L.key[j];j-=dk){compare_Time++;L.key[j+dk]=L.key[j];move_Time++;}L.key[j+dk]=L.key[0];}}voidShellSort(SqList&L,intdlta[],intt){intcompare_Time=0,move_Time=0;//按增量序列dl[0]--dl[t-1]对顺序表L作哈希排序for(intk=0;kt;k++){ShellInsert(L,dlta[k],compare_Time,move_Time);cout第k+1趟排序结果：;OutPut(L);}编辑版wordcout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}voidHeapAdjust(SqList&L,ints,intm,int&compare_Time,int&move_Time){//对顺序表做查找，从值最大的孩子结点向下筛选，找到最大值intrc=L.key[s];for(intj=2*s;j=m;j*=2){if(jm&&L.key[j]=L.key[j+1])//找到值相对较大的孩子结点，并依次向下筛选{j++;}compare_Time++;if(rcL.key[j])break;//如果rc最大则推出while循环L.key[s]=L.key[j];//最大值赋值s=j;//交换位置move_Time++;}L.key[s]=rc;}编辑版wordvoidHeapSort(SqList&L){//对顺序表L进行堆排序intvalue,i;intk=0;intcompare_Time=0,move_Time=0;for(i=L.length/2;i0;i--)//把L.key[1...L.length]调整为大顶堆HeapAdjust(L,i,L.length,compare_Time,move_Time);for(i=L.length;i1;--i){value=L.key[1];L.key[1]=L.key[i];L.key[i]=value;HeapAdjust(L,1,i-1,compare_Time,move_Time);//将L.key[1...i-1]重新调整为大顶堆k++;cout第k趟排序结果：;OutPut(L);}cout比较次数为：compare_Timeendl;cout移动次数为：move_Timeendl;}intmain(){编辑版wordintchoice;SqListsq,