10.1几种基本排序算法的实现

《10.1几种基本排序算法的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验题目：几种基本排序算法的实现姓名：张耀班级：计嵌151学号：1513052017一、实验目的实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用内部排序算法，比较各算法的比较次数和移动次数。二、数据结构设计(1)设计待排序记录的存储结构。(2)设计待排序数据的存储结构。(3)输入：待排序数据的数据个数和数据可由键盘输入，也可由程序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。(4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字比较次数和移

2、动次数。三、算法设计与N-S图算法设计：编写一个主函数main()，在主函数中设计一个简单的菜单，分别调用6种内部排序算法。为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数；设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程序生成数据，以便随时更换排序数据，并按照不同要求对排序数

3、据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。一、程序清单#includeusingnamespacestd;voidshowMenu(){cout<<"*菜单*"<

4、序"<>n;sl.length=n;sl.key=newint[sl.length+1];cout<<"请输入数据："<

5、n>>sl.key[i];}}voidCopy(SqList&L1,SqList&L2){L2.length=L1.length;L2.key=newint[L1.length+1];for(inti=1;i<=L1.length;i++){L2.key[i]=L1.key[i];}}voidOutPut(SqList&L){for(intj=1;j<=L.length;++j)cout<

6、ntk=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;for(j=i-2;L.key[0]<=L.key[j];--j){compare_Time++;L.key[j+1]=L.key[j];//记录后移move_Tim

7、e++;}L.key[j+1]=L.key[0];//插入到正确位置k++;cout<<"第"<

8、)//用i控制比较趟数共n-1趟{intt;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++