合肥学院
计算机科学与技术系
课程设计报告
2017～2018 学年第一学期
课学学专指
业导
班教生
姓
程 数据结构与算法
内部排序算法比较
操彦 1504012027
计算机科学与技术系15级 2 班
名 号 级 师
课程设计名称
2017 年 9 月
1、问题分析和任务定义
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。 2、数据结构的选择和概要设计
一．可能排序表的抽象数据类型定义： ADT OrderableList｛
数据对象：D=｛|∈IntegerSet，i=1，2，??，n，n≥0｝ 数据关系：R1=｛<
,|
,∈D,i=2,??n｝
基本操作： InitList（n）
操作结果：构造一个长度为n，元素值依次为1，2，??，n的有序表。 RandomizeList(d,isInverseOrder)
操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0≤d≤8）级随机打乱。d为0时表不打乱，d越大，打乱程度越高。 RecallList（）
操作结果：恢复最后一次用RandomizeList随机大乱的可排序表。 ListLength（）
操作结果：返回可排序的长度。 ListEmpty（）
操作结果：若可排序表为空表，则返回True，否则返回False。 BubbleSort（&c，&s）
操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。 InsertSort（&c，&s）
操作结果：进行插入排序，返回关键字比较次数c和移动次数s。 SelectSort（&c，&s）
操作结果：进行选择排序，返回关键字比较次数c和移动次数s。 QuickSort（&c，&s）
操作结果：进行快速排序，返回关键字比较次数c和移动次数s。 ShellSort（&c，&s）
操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。 HeapSort（&c，&s）
操作结果：进行堆排序，返回关键字比较次数c和移动次数s。 ListTraveres（visit()）
操作结果：依次对L中的每个元素调用函数visit（）。 ｝ADT OrderableList 二．概要设计： 1.冒泡排序：
冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，
将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 2.直接插入排序：
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已牌号序的有序表中，从而得到一个新的、记录数增1的有序表。 3.简单选择排序： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环。 4.希尔排序：
希尔排序又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较前述集中排序方法有较大的改进。它的基本思想是：先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 5.堆排序：
由二叉堆的定义可知，堆顶元素（即二叉堆的根节点）一定为堆中的最大值或最小值，因此如果我们输出堆顶元素后，将剩余的元素再调整为二叉堆，继而再次输出堆顶元素，再将剩余的元素调整为二叉堆，反复执行该过程，这样便可输出一个有序序列，这个过程我们就叫做堆排序。 6.归并排序：
归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。归并排序中一般所用到的是2-路归并排序，即将含有n个元素的序列看成是n个有序的子序列，每个子序列的长度为1，而后两两合并，得到n/2个长度为2或1的有序子序列，再进行两两合并。。。直到最后由两个有序的子序列合并成为一个长度为n的有序序列。2-路归并的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。 7.快速排序：
快速排序的基本实现思想就是将当前待排序列分成两个部分、一个值。一个值：就是选定出一个值作为被比较的元素。两个部分：所有比该被选定元素大的部分都去该元素的右边，所有比被选定元素小的部分都去该元素的左边。这样我们就确定了该元素在这个待排序列中的位置，其实也就是我们已经将这个元素“排好了”。
3、详细设计和编码 1.冒泡排序：
void gensort(int b[],int n) {
int i,j;int s=0,t=0; for(i=0;i for(j=i+1;j t++; if(b[i]>b[j]) { int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}} cout<<\移动次数=\比较次数=\} 2.直接插入排序： void insertsort(sqlist b,int n) { int i,j;int s=0,t=0; for(i=2;i b[0]=b[i]; s++; j=i-1; t++; while(b[0].key b[j+1]=b[j]; j--; s++; t++; } b[j+1]=b[0]; s++; } cout<<\移动次数=\比较次数=\} 3.简单选择排序： void gentsort(int b[],int n) { int i,j,k; int s=0,t=0; for(i=0;i k=i; for(j=i+1;j if(b[k]>b[j]) {k=j;} } if(k!=i) {int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }} cout<<\移动次数=\比较次数=\} 4.希尔排序： void shellsort(sqlist b,int n) { int i,j,gap; rec x; int s=0,t=0; gap=n/2; while(gap>0) { for(i=gap+1;i j=i-gap; while(j>0) { t++; if(b[j].key>b[j+gap].key) { x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; } else j=0; gap=gap/2; }} cout<<\移动次数=\比较次数=\}} 5.堆排序： void sift(sqlist r,int s,int m) { int j; rec x; x=r[s]; for(j=2*s;j<=m;j*=2) {q++;