搜索
合肥学院计算机科学与技术系课程设计报告2017～2018学年第一学期课程数据结构与算法课程设计名称内部排序算法比较学生姓名操彦学号1504012027专业班级计算机科学与技术系15级2班指导教师2017年9月1、问题分析和任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。2、数据结构的选择和概要设计一．可能排序表的抽象数据类型定义：ADTOrderableList｛数据对象：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（）。｝ADTOrderableList二．概要设计：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.冒泡排序：voidgensort(intb[],intn){inti,j;ints=0,t=0;for(i=0;in-1;i++){for(j=i+1;jn;j++){t++;if(b[i]b[j]){inttemp=b[i];b[i]=b[j];b[j]=temp;s+=3;}}}cout移动次数=s,比较次数=tendl;}2.直接插入排序：voidinsertsort(sqlistb,intn){inti,j;ints=0,t=0;for(i=2;in;i++){b[0]=b[i];s++;j=i-1;t++;while(b[0].keyb[j].key){b[j+1]=b[j];j--;s++;t++;}b[j+1]=b[0];s++;}cout移动次数=s,比较次数=tendl;}3.简单选择排序：voidgentsort(intb[],intn){inti,j,k;ints=0,t=0;for(i=0;in-1;i++){k=i;for(j=i+1;jn;j++){t++;if(b[k]b[j]){k=j;}}if(k!=i){inttemp=b[k];b[k]=b[i];b[i]=temp;s+=3;}}cout移动次数=s,比较次数=tendl;}4.希尔排序：voidshellsort(sqlistb,intn){inti,j,gap;recx;ints=0,t=0;gap=n/2;while(gap0){for(i=gap+1;in;i++){j=i-gap;while(j0){t++;if(b[j].keyb[j+gap].key){x=b[j];b[j]=b[j+gap];b[j+gap]=x;j=j-gap;s+=3;}elsej=0;gap=gap/2;}}cout移动次数=s,比较次数=tendl;}}5.堆排序：voidsift(sqlistr,ints,intm){intj;recx;x=r[s];for(j=2*s;j=m;j*=2){q++;if(jm&&(r[j].keyr[j+1].key))++j;q++;if(!(x.keyr[j].key))break;r[s]=r[j];s=j;p++;}r[s]=x;p++;}voidheapsort(sqlist&r,intm){inti;recw;for(i=m/2;i0;--i)sift(r,i,m);for(i=m;i1;--i){w=r[i];r[i]=r[1];r[1]=w;p+=3;sift(r,1,i-1);}}voidsorting(sqlist&r,intt){BeforeSort();heapsort(r,t);display(p,q);}voidinit(inta[]){//随机生成N个整数并inti;srand((unsignedint)time(NULL));for(i=0;iN;i++)a[i]=rand()%99+1;}6.归并排序：#includestdio.hvoidcutTwo(intsourceArr[],int*tempArr[],intstart,intend);voidmerge(intsourceArr[],int*tempArr[],intstart,intmid,intend);intmain(intargc,char*argv[]){inta[8]={50,10,20,30,70,40,80,60};int*b[8]={};inti;cutTwo(a,b,0,8);for(i=0;i8;i++){printf(%d,a[i]);}return0;}/*归并排序算法：*/voidmerge(intsourceArr[],int*tempArr[],intstart,intmid,intend){//当前我们有一个源数组，我们在比较时将这个源数组一分为二进行比较归并排序/*因为我们要进行归并排序，所以我们需要两个指针分别指向两个子序列的开始位置，即start指向左边部分的开始位置，mid+1指向右边部分的开始位置，我们还需要一个k的下标，用于存储我们交换过来的数组到临时数组tempArr[]*/inti=start;//定义一个i下标，用于表示左边部分开始的位置下标intj=mid+1;//定义一个j下标，用于表示右边部分开始的位置下标intk=0;/*因为我们在比较时是不断的比较，直到一个子序列到达最后，所以我们应该用while循环来做，结束条件：无非就是左边序列到头了或者是右边序列到头了，即：i=mid&&j=end只有在这两个条件都成立的条件下说明两个子序列都没有到头*/while(i=mid&&j=end){//当i=mid+1或者j=end+1时说明子序列中有一个到头了，则跳出循环if(sourceArr[i]=sourceArr[j]){//表示当前i比较小，那么我们就将小的值赋给ktempArr[k]=sourceArr[i];k=k+1;i=i+1;}else{tempArr[k]=sourceArr[j];k=k+1;j=j+1;}/*不能将k,i,j的加1操作放在ifelse判断的外面，因为我们在进行比较的时候，只是将下标所指的数字小的放在左边，将下标所指的数字大的不动，因为我们小的下标加1后还要和刚才下标所指的数字再次进行比较，如果放在外面，那么我们的比较的对象不对了（因为的大的数字的下标加1了，前面的一个数字没有进行比较）*/}/*当有一个子序列到头以后，我们就要将剩余没到头的子序列的剩余元素放到k的右边，因为剩余的肯定是已经有序的，且肯定比已经到头的子序列的全部元素都要大的。*/while(j=end){//i==mid+1&&因为左边序列i跳出循环的条件肯定是当前i=mid+1了，则我们移动右边j的子序列就好了tempArr[k]=sourceArr[j];k++;j++;}while(i=mid){//&&j==end+1则此时表示当前跳出循环的是j右边的子序列，则我们移动左边的i的子序列tempArr[k]=sourceArr[i];k++;i++;}intm;for(m=0;mk;m++){sourceArr[start+m]=tempArr[m];}}/*上述操作完成仅仅是完成了对一个大的序列中一部分的排列，因为我们的做法是对整个的序列进行二分，二分之后对子序列进行归并排序*/voidcutTwo(intsourceArr[],int*tempArr[],intstart,intend){if(startend){intmid;//设置一个取中间的变量mid=(start+end)/2;cutTwo(sourceArr,tempArr,start,mid);cutTwo(sour