内部排序算法的实现与比较

实验四：内部排序算法的实现与比较一、问题描述1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。（2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。（3)对结果作出简要分析。3．测试数据：随机函数产生。二、需求分析1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。4．测试数据要求：随机函数产生的N（N=30000）个随机整数。三、概要设计1.所用到得数据结构及其ADT为了实现上述功能，应以一维数组表示集合数据类型。ints[N];intcompare[6]={0},move[6]={0},D[N]={0},RS[N]={0};基本操作：数组赋值：for(i=1;iN;i++){s[i]=rand()%100;printf(%d\t,s[i]);}voidcopys(intS[],intRS[],intn)//将s[]的值赋给RS[],voidSelectSort(intRS[],intn)//直接选择排序voidBubbleSort(intRS[],intn)//冒泡排序voidInsertSort(intRS[],intn)//直接插入排序intQuickSort(intRS[],intlow,inthigh)//快速排序voidQuickSortprint(intRS[],intn)//输出快速排序后的结果voidShellsert(intRS[],intm,intn)//一趟希尔排序，按间隔m划分子序列voidShellsort(intRS[],intn)//希尔排序voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列voidMSort(intRS[],intlow,inthigh)//归并排序2.主程序流程及其模块调用关系开始初始界面显示i=1iNs[i]=rand()%100数组赋值i++SelectSort(compare,5);SelectSort(move,5);i=1i=5输出compare[i])的值i++i=1i=5输出move[i])的值i++YNYYNNJ=1J=2J=3J=4J=5J=6SelectSort(RS,N-1);BubbleSort(RS,N-1);InsertSort(RS,N-1);QuickSortprint(RS,N-1);Shellsort(RS,N-1);MSort(RS,1,N-1);J=7J=8NNNNNNYYYYYYYNvoidSelectSort(intRS[],intn)//直接选择排序模块开始i=1ink=i;j=i+1j=nRS[j]RS[k]k=j;compare[0]++;j++k!=iRS[0]=RS[k];RS[k]=RS[i];RS[i]=RS[0];move[0]+=3;i++输出排序后结果结束YNYYNNvoidBubbleSort(intRS[],intn)//冒泡排序模块开始i=1i=nflag=True;j=1j=n-iRS[j+1]RS[j]flag=False;RS[0]=RS[j];RS[j]=RS[j+1];RS[j+1]=RS[0];move[1]+=3;compare[1]++;j++flag==True输出排序后结果i++结束YNYYNNvoidInsertSort(intRS[],intn)//直接插入排序模块开始i=2i=nRS[0]=RS[i]j=i-1;move[2]++;RS[0]RS[j]compare[2]++;RS[j+1]=RS[j];move[2]++;j--;RS[j+1]=RS[0];move[2]++;i++输出排序后结果结束YNYNintQuickSort(intRS[],intlow,inthigh)//快速排序模块开始n=high;i=low;j=high;RS[0]=RS[i];move[3]++;ijRS[j]=RS[0]&&jij--;compare[3]++;compare[3]++;jiRS[i]=RS[j];move[3]++;i++;RS[i]=RS[0]&&jii++;compare[3]++;compare[3]++;jiRS[j]=RS[i];move[3]++;j--;RS[i]=RS[0];move[3]++;lowiHigh=i-1ihighLow=j+1输出排序后的结果结束YNNNNNNNYYYYYYvoidShellsert(intRS[],intm,intn)//一趟希尔排序，按间隔m划分子序列开始i=mi=n/mtemp=RS[i];j=i;j=m&&tempRS[j-m]compare[4]++;RS[j]=RS[j-m];move[4]++;j-=m;RS[j]=temp;move[4]++;i++结束YNNYvoidShellsort(intRS[],intn)//希尔排序模块开始m=n/2;m=1Shellsert(RS,m,n);m=(m==2?1:(m/2));输出排序后结果结束YNvoidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列开始i=low;j=mid+1;k=low;i=mid&&j=highRS[i]=RS[j]D[k]=RS[i];i++;k++;D[k]=RS[j];j++;k++;compare[5]++;move[5]++;i=midn1=k,n2=in1=high&&n2=midD[n1]=RS[n2];move[5]++;n1++,n2++n1=k,n2=jn1=high&&n2=highD[n1]=RS[n2];move[5]++;n1++,n2++mid=lowmid=highRS[mid]=D[mid]move[5]++;mid++结束YNNNNNYYYY模块调用voidmain()主函数模块voidcopys(intS[],intRS[],intn)将s[]的值赋给RS[],voidSelectSort(intRS[],intn)//直接选择排序voidBubbleSort(intRS[],intn)//冒泡排序voidInsertSort(intRS[],intn)//直接插入排序voidQuickSortprint(intRS[],intn)//快速排序后的结果Shellsort(RS,N-1);希尔排序MSort(RS,1,N-1);归并排序Merge(RS,low,mid,high);将两个有序序列归并为一个有序序列voidShellsert(intRS[],intm,intn)//一趟希尔排序，按间隔m划分子序列intQuickSort(intRS[],intlow,inthigh)//快速排序四、详细设计1.实现每个操作的伪码，重点语句加注释1）voidcopys(intS[],intRS[],intn)//数组复制{inti;for(i=1;in;i++)RS[i]=S[i];}2）直接选择排序voidSelectSort(intRS[],intn)//直接选择排序{inti,j,k;for(i=1;in;i++){k=i;for(j=i+1;j=n;j++){if(RS[j]RS[k])k=j;compare[0]++;}if(k!=i){RS[0]=RS[k];RS[k]=RS[i];RS[i]=RS[0];move[0]+=3;}}printf(直接选择排序后的结果：);for(i=1;i=n;i++)printf(%d\t,RS[i]);printf(\n);printf(关键字参加的比较次数：%d,关键字的移动次数：%d\n,compare[0],move[0]);printf(\n);}3）冒泡排序voidBubbleSort(intRS[],intn)//冒泡排序{inti,j,flag;for(i=1;i=n;i++){flag=True;for(j=1;j=n-i;j++){if(RS[j+1]RS[j]){flag=False;RS[0]=RS[j];RS[j]=RS[j+1];RS[j+1]=RS[0];move[1]+=3;}compare[1]++;}if(flag==True)break;}printf(冒泡排序后的结果：);for(i=1;i=n;i++)printf(%d\t,RS[i]);printf(\n);printf(关键字参加的比较次数：%d,关键字的移动次数：%d\n,compare[1],move[1]);printf(\n);}4）直接插入排序voidInsertSort(intRS[],intn)//直接插入排序{inti,j;for(i=2;i=n;i++){RS[0]=RS[i];j=i-1;move[2]++;while(RS[0]RS[j]){compare[2]++;RS[j+1]=RS[j];move[2]++;j--;}compare[2]++;RS[j+1]=RS[0];move[2]++;}printf(直接插入排序后的结果：);for(i=1;i=n;i++)printf(%d\t,RS[i]);printf(\n);printf(关键字参加的比较次数：%d,关键字的移动次数：%d\n,compare[2],move[2]);printf(\n);}5）快速排序intQuickSort(intRS[],intlow,inthigh)//快速排序{inti,j,n;n=high;i=low;j=high;RS[0]=RS[i];move[3]++;while(ij){while(RS[j]=RS[0]&&ji){j--;compare[3]++;}compare[3]++;if(ji){RS[i]=RS[j];move[3]++;i++;}while(RS[i]=RS[0]&&ji){i++;compare[3]++;}compare[3]++;if(ji){RS[j]=RS[i];move[3]++;j--;}}RS[i]=RS[0];move[3]++;if(lowi)QuickSort(RS,low,i-1);if(ihigh)QuickSort(RS,j+1,high);}6）输出快速排序后的结果voidQuickSortprint(intRS[],intn)//输出快速排序后的结果{inti;QuickSort(RS,1,n);printf(快速排序后的结果：);for(i=1;i=n;i++)printf(%d\t,RS[i]);printf(\n);printf(关键字参加的比较次数：%d,关键字的移动次数：%d\n,compare[3],move[3]);printf(\n);}7）一趟希尔排序，按间隔m划分子序列voidShellsert(intRS[],intm,intn)//一趟希尔排序