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

1、实验四部排序算法的实现与比较1、 问题描述1 实验题目： 在教科书中， 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。 试通过随机数据比较各算法的关键字比较次数和关键字移动次数， 以取得直观感 受。2 基本要求： （ 1 ）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。（2利用随机函数产生 N （N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为 3 次移动） 。（ 3） 对结果作出简要分析。3 测试数据：随机函数产生。2、 需求分析1 程序所能达

2、到的基本可能：通过随机数据产生N 个随机数，作为输入数据作比较；对常用的内部排序算法： 直接插入排序、 简单选择排序、 冒泡排序、 快速排序、 希尔排序、 归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为 3 次移动） 。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。2 .输入的形式及输入值范围：随机函数产生的N （N=30000）个随机整数。3 输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。4 .测试数据要求：随机函数产生的N （N=30000）个随机整数。3、 概要设计1.

3、所用到得数据结构及其ADT为了实现上述功能，应以一维数组表示集合数据类型。int sN;int compare6=0,move6=0,DN=0,RSN=0;基本操作：数组赋值：for(i=1;i<N;i+) void copys(int S,int RS,int n)/void SelectSort(int RS,int n) / void BubbleSort(int RS,int n)/ void InsertSort(int RS,int n) / int QuickSort(int RS,int low,int high)/ void QuickSortprint(int RS,

4、int n)/ void Shellsert(int RS,int m,int n)/ void Shellsort(int RS,int n)/si=rand()%100;printf("%dt",si);将 s 的值赋给 RS,直接选择排序冒泡排序直接插入排序快速排序输出快速排序后的结果一趟希尔排序，按间隔m划分子序列希尔排序2. 主程序流程及其模块调用关系直接选择排序模块void SelectSort(int RS,int n) /开始冒泡排序模块void BubbleSort(int RS,int n)开始i=1flag=False;RS0=RSj;RSj=RSj+

5、1;RSj+1=RS0; move1+=3;compare1+; j+直接插入排序模块void InsertSort(int RS口,int n) /int QuickSort(int RS,int low,int high)/快速排序模块void Shellsert(int RS,int m,int n)/一趟希尔排序，按间隔 m划分子序列void Shellsort(int RS,int n)/希尔排序模块void Merge(int RS,int low,int mid,int high)/将两个有序序列归并为一个有序序列开始结束模块调用四、1.1) 详细设计实现每个操作的伪码，重点语句

6、加注释数组复制void copys(int S,int RS,int n)/int i;for(i=1;i<n;i+)RSi=Si；2)直接选择排序直接选择排序void SelectSort(int RS,int n) / int i,j,k；for(i=1;i<n;i+)k=i;for(j=i+1;j<=n;j+)if(RSj<RSk) k=j； compare0+;if(k!=i)RS0=RSk;RSk=RSi;RSi=RS0;move0+=3;printf(" 直接选择排序后的结果： ");for(i=1;i<=n;i+)printf(&

7、quot;%dt",RSi);printf("n");%dn",compare0,move0);printf("关键字参加的比较次数：d,关键字的移动次数:printf("n");3)冒泡排序void BubbleSort(int RS,int n)/ 冒泡排序int i,j,flag;for(i=1;i<=n;i+)flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)flag=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move1+=3; compar

8、e1+;if(flag=True) break;printf(" 冒泡排序后的结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");%dn",compare1,move1);printf("关键字参加的比较次数：d,关键字的移动次数:printf("n");4）直接插入排序直接插入排序void InsertSort(int RS,int n) / int i,j;for(i=2;i<=n;i+)RS0=RSi;j=i-1;move2

9、+;while(RS0<RSj) compare2+;RSj+1=RSj;move2+;j-;compare2+;RSj+1=RS0;move2+;printf(" 直接插入排序后的结果：for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf(" 关键字参加的比较次数： printf("n");5)快速排序int QuickSort(int RS,int low,int high)/int i,j,n;n=high;i=low;");%d,关键

10、字的移动次数:快速排序%dn",compare2,move2);j=high;RS0=RSi;move3+;while(i<j)while(RSj>=RS0&&j>i)j-;compare3+; compare3+;if(j>i) RSi=RSj;move3+;i+;while(RSi<=RS0&&j>i)i+;compare3+;compare3+;if(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<

11、;high)QuickSort(RS,j+1,high);6)输出快速排序后的结果void QuickSortprint(int RS,int n)/输出快速排序后的结果 int i;QuickSort(RS,1,n);printf(" 快速排序后的结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare3,move3);printf("n");7) 一趟希尔

12、排序，按间隔m划分子序列void Shellsert(int RS,int m,int n)一趟希尔排序，按间隔m划分子序列int i,j,temp;for(i=m;i<=n/m;i+)temp=RSi;j=i;while(j>=m&&temp<RSj-m) compare4+;RSj=RSj-m;move4+;j-=m;RSj=temp;move4+;8)希尔排序void Shellsort(int RS,int n)/希尔排序int m,i;m=n/2;while(m>=1)/ 循环直到m为0Shellsert(RS,m,n);m=(m=2?1:(m

13、/2);/ 缩小增进量printf(" 希尔排序后的结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare4,move4);printf("n");9)将两个有序序列归并为一个有序序列void Merge(int RS,int low,int mid,int high)/将两个有序序列归并为一个有序序列int i,j,k;int n1,n2;i=low;j=

14、mid+1;k=low;while(i<=mid&&j<=high)/ 两两比较if(RSi<=RSj)Dk=RSi;i+;k+;elseDk=RSj;j+;k+;compare5+;move5+;if(i<=mid)for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+)Dn1=RSn2;move5+;elsefor(n1=k,n2=j;n1<=high&&n2<=high;n1+,n2+)Dn1=RSn2;move5+;for(mid=low;mid<=high;m

15、id+)RSmid=Dmid;move5+;10 )归并排序void MSort(int RS,int low,int high)/归并排序int mid;if(low<high)mid=(low+high)/2;MSort(RS,low, mid);MSort(RS, mid+1,high);Merge(RS,low,mid,high);11)主函void main()int i,j,sN;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);printf(

16、" 实验名称：实验四：内部排序算法的实现与比较n");printf(" 姓名：王亚文n");printf("=n");printf(" 程序运行开始， ");printf("Current local time and date:%s",asctime(timeinfo);printf(" 产生的随机数为： n");for(i=1;i<N;i+)si=rand()%100;printf("%dt",si);printf("n");

17、docopys(s,RS,N);printf(" 请选择所需排序方法： ");printf("n");printf("1. 选择法 ,2. 冒泡法 ,3. 插入法 ,4. 快速法 , 5. 希尔排序法,6. 归并排序法，7. 输出比较信息， 8. 退出 n");scanf(" %d",&j);switch(j)case 1:SelectSort(RS,N-1);break;case 2:BubbleSort(RS,N-1);break;case 3:InsertSort(RS,N-1);break;case

18、 4:QuickSortprint(RS,N-1);break;case 5:Shellsort(RS,N-1);break;case 6:MSort(RS,1,N-1);printf(" 归并排序后的结果： ");for(i=1;i<N;i+)printf("%dt",Di);printf("n");printf(" 关 键 字 参 加 的 比 较 次 数 ：%d, 关 键 字 的 移 动 次数： %dn",compare5,move5);printf("n");break;case 7

19、:SelectSort(compare,5);SelectSort(move,5);printf(" 关键字参加的比较次数:n");for(i=1;i<=5;i+)printf("%dt",comparei);printf("n");printf(" 关键字的移动次数： n");for(i=1;i<=5;i+)printf("%dt",movei);printf("n");break;case 8:printf("Current local time a

20、nd date:%s",asctime(timeinfo);exit(0);break;while(1);五、 调试分析1. 设计与调试过程中遇到的问题分析、体会调试过程： 由于本次程序设计的数据和模块比较多，所以采用分块调试的方法，在编写完一个内部排序算法后， 为了验证是否排序成功以及所输出的关键字比较次数和移动次数是否正确， 采用先定义一个需要排序9 个数字的数组， S10=0 ， 1 ， 2， 3， 4， 5， 6， 7， 8， 9 和 S10=0 ， 9， 8， 7，6， 5， 4， 3， 2， 1, 用这两个数组检验程序的正确性与否。调试步骤，程序及相关结果如下：1)直接选

21、择排序：#include <stdio.h>#include <malloc.h>#include <stdlib.h>void SelectSort(int RS,int n) /直接选择排序int i,j,k,move=0,compare=0;for(i=1;i<n;i+)k=i;for(j=i+1;j<=n;j+)if(RSj<RSk) k=j；compare+;if(k!=i)RS0=RSk;RSk=RSi;RSi=RS0;move+=3;printf("直接选择排序后的结果：");for(i=1;i<=n

22、;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare,move);printf("n");void main()int s10=0,12345,6,7,8,9;SelectSort(s,9);s10=0,1,2,3,4,5,6,7,8,9;区接选择排序后的结果* 1 23456?8案键字参加的比较次熟36,关键字的移动次期0S10=0,9,8,7,6,5,4,3,2,12)冒泡排序#include <stdio.

23、h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1void BubbleSort(int RS,int n)/冒泡排序int i,j,flag,move=0,compare=0; for(i=1;i<=n;i+)flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)flag=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move+=3; compare+;if(flag=True) break;printf(&

24、quot;冒泡排序后的结果："力for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare,move);printf("n");void main()int s10=0,12345,6,7,8,9;BubbleSort(s,9);s10=0,1,2,3,4,5,6,7,8,9s10=0,9,8,7,6,5,4,3,2,1;3)直接插入排序 #include <stdio.h>

25、;#include <malloc.h>#include <stdlib.h>#define False 0#define True 1void InsertSort(int RS口,int n) /直接插入排序int i,j,compare=0,move=0;for(i=2;i<=n;i+) RS0=RSi;j=i-1;move+;while(RS0<RSj)compare+;RSj+1=RSj;move+;j-;compare+; RSj+1=RS0; move+;printf(" 直接插入排序后的结果：for(i=1;i<=n;i+)

26、printf("%dt",RSi); printf("n");printf(" 关键字参加的比较次数： printf("n");");%d,关键字的移动次数:%dn",compare,move);void main()int s10=0,9,8,7,6,5,4,3,2,1;InsertSort(s,9);s10=0,9,8,7,6,5,4,3,2,1;s10=0,1,2,3,4,5,6,7,8,9;4)快速排序#include <stdio.h> #include <malloc.h&g

27、t;#include <stdlib.h>#define False 0#define True 1int compare6=0,move6=0;快速排序int QuickSort(int RS,int low,int high)/int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i<j)while(RSj>=RS0&&j>i)j-;compare3+;compare3+;if(j>i)RSi=RSj;move3+;i+;while(RSi<=RS0&&j>i)i

28、+;compare3+;compare3+;if(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<high)QuickSort(RS,j+1,high);void QuickSortprint(int RS,int n)/输出快速排序后的结果 int i;QuickSort(RS,1,n);printf(" 快速排序后的结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n&qu

29、ot;);printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare3,move3);printf("n");void main()int s10=0,9,8,7,6,5,4,3,2,1;QuickSortprint(s,9);s10=0,9,8,7,6,5,4,3,2,1;5)希尔排序#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1int compare6=0,move6=

30、0;void Shellsert(int RS,int m,int n)一趟希尔排序，按间隔m划分子序列int i,j,temp;for(i=m;i<=n/m;i+)temp=RSi;j=i;while(j>=m&&temp<RSj-m) compare4+;RSj=RSj-m;move4+;j-=m; RSj=temp; move4+; void Shellsort(int RS,int n)/希尔排序int m,i;m=n/2;while(m>=1)/ 循环直到m为0 Shellsert(RS,m,n);m=(m=2?1:(m/2);/ 缩小增进量

31、printf(" 希尔排序后的结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare4,move4);printf("n");void main()int s10=0,9,8,7,6,5,4,3,2,1;Shellsort(s,9);s10=0,9,8,7,6,5,4,3,2,1;s10=0,1,2,3,4,5,6,7,8,9;6)归并排序#include

32、<stdio.h>#include <malloc.h>#include <stdlib.h>#define False 0#define True 1int compare6=0,move6=0,D10=0;void Merge(int RS,int low,int mid,int high)/将两个有序序列归并为一个有序序列int i,j,k;int n1,n2;i=low;j=mid+1;k=low;while(i<=mid&&j<=high)/ 两两比较if(RSi<=RSj)Dk=RSi;i+;k+;elseDk=

33、RSj;j+;k+;compare5+;move5+;if(i<=mid)for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+)Dn1=RSn2;move5+;elsefor(n1=k,n2=j;n1<=high&&n2<=high;n1+,n2+)Dn1=RSn2;move5+;for(mid=low;mid<=high;mid+)RSmid=Dmid;move5+;void MSort(int RS,int low,int high)/归并排序int mid;if(low<high)mid=

34、(low+high)/2;MSort(RS,low, mid);MSort(RS, mid+1,high);Merge(RS,low,mid,high);void main()int s10=0,9,8,7,6,5,4,3,2,1,i;MSort(s,1,9);printf(" 归并排序后的结果： ");for(i=1;i<10;i+)printf("%dt",Di);printf("n");printf(" 关 键 字 参 加 的 比 较 次 数 ：%d, 关 键 字 的 移 动 次数： %dn",comp

35、are5,move5);printf("n");s10=0,9,8,7,6,5,4,3,2,1；调试过程中遇到的问题：1)这个内部排序算法的实现与比较程序设计中，大部分排序算法在书上已经给了详细的程序只需要稍加更改，所以在编写排序程序时并没有太大的问题，唯一的问题是 for(mid=low;mid<=high;mid+)RSmid=Dmid;move5+;这段程序一开始书上是放在 MSort 这个程序中， 但是我放在这个程序里输出的排序并不是按照升序排列的，将这段程序改在 merge 里， 程序就能正常输出了， 还有一个问题是随机数产生的数字是放在数组里的， 执行完第

36、一个排序后再想去执行下一个排序程序时再用原来的数组就已经不是利用随 机函数产生的数组了而是经过排序后形成的有序数组， 这就影响了下一个程序的正常运行， 他所输出的关键字的比较次数和移动次数就不是我们所想的随机函数产生的数组排序时的比较次数和移动次数，为了解决这个问题考虑另外定义一个数组，先利用随机函数产生一个随机数组，每次执行排序前都将随机数组中的数值赋给另一个数组，对另外的数组执行排序程序，这就可以有效解决输出的关键字的比较次数和移动次数不对的问题。这样第一步显示保证每个程序都可以将一个无序的序列排序成为有序序列。2)在完成了第一步之后就可以进行第二部，进行关键字的比较次数和移动次数的计算，

37、一开始我是将每一个程序中都定义一个compare和move值，这种办法在前几个程序中并没有什么问题，也没有什么不方便，但在之后一个函数需要调用另一个函数时， 因为一个函数只能返回一个值，这个对 于这 个需要返 回 两个值 的 程序 就不适 用 了 ， 所 以 就考虑定义 了 两个数 组 ， int compare6=0,move6=0， 这样就解决了这个不能再一个程序中返回两个值得问题， 同时也大大简化了后面需要对各种内部排序算法所产生的关键字的比较次数和移动次数的排序与输出， 一举 两得。 这个程序是通过随机数据产生N 个随机数，作为输入数据作比较； 对常用的内部排序算法： 直接插入排序、简

38、单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键 字参加的比较次数和关键字的移动次数(关键字交换记为 3 次移动) 。最后结果输出各种排序算法 的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。 六、测试结果七、附录#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <time.h>#define N 100#define False 0#define True 1int compare6=0,move6=0,DN=0,RSN=0;

39、void copys(int S,int RS,int n) int i;for(i=1;i<n;i+) RSi=Si; void SelectSort(int RS,int n) /直接选择排序int i,j,k; for(i=1;i<n;i+) k=i;for(j=i+1;j<=n;j+) if(RSj<RSk) k=j;compare0+;if(k!=i)RS0=RSk;RSk=RSi;RSi=RS0;move0+=3;printf(" 直接选择排序后的结果： ");for(i=1;i<=n;i+)printf("%dt&quo

40、t;,RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数:printf("n");void BubbleSort(int RS,int n)/ 冒泡排序int i,j,flag;for(i=1;i<=n;i+)flag=True;for(j=1;j<=n-i;j+)if(RSj+1<RSj)flag=False;RS0=RSj;RSj=RSj+1;RSj+1=RS0;move1+=3; compare1+;if(flag=True) break;printf(" 冒泡排序后的

41、结果： ");for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数:%dn",compare0,move0);%dn",compare1,move1);printf("n");void InsertSort(int RS,int n) /直接插入排序int i,j;for(i=2;i<=n;i+)RS0=RSi;j=i-1;move2+;while(RS0<RSj)compare2

42、+;RSj+1=RSj;move2+;j-;compare2+;RSj+1=RS0;move2+;printf(" 直接插入排序后的结果：for(i=1;i<=n;i+)printf("%dt",RSi);printf("n");printf(" 关键字参加的比较次数：printf("n");int QuickSort(int RS,int low,int high)/ int i,j,n;n=high;i=low;j=high;RS0=RSi;move3+;while(i<j)while(RSj>

43、;=RS0&&j>i)");%d,关键字的移动次数:快速排序%dn",compare2,move2);j-;compare3+;compare3+;if(j>i)RSi=RSj; move3+; i+;while(RSi<=RS0&&j>i) i+;compare3+;compare3+;if(j>i)RSj=RSi;move3+;j-;RSi=RS0;move3+;if(low<i)QuickSort(RS,low,i-1);if(i<high)QuickSort(RS,j+1,high);输出快速

44、排序后的结果%d,关键字的移动次数：dn",compare3,move3);一趟希尔排序，按间隔m划分子序列void QuickSortprint(int RS,int n)/ int i;QuickSort(RS,1,n);printf(" 快速排序后的结果： ");for(i=1;i<=n;i+) printf("%dt",RSi); printf("n");printf(" 关键字参加的比较次数： printf("n");void Shellsert(int RS,int m,int

45、 n)/ int i,j,temp;for(i=m;i<=n/m;i+)temp=RSi;j=i;while(j>=m&&temp<RSj-m) compare4+;RSj=RSj-m;move4+;j-=m;RSj=temp;move4+;void Shellsort(int RS,int n)/希尔排序int m,i;m=n/2;while(m>=1)/ 循环直到m为0Shellsert(RS,m,n);m=(m=2?1:(m/2);/ 缩小增进量printf(" 希尔排序后的结果： ");for(i=1;i<=n;i+)p

46、rintf("%dt",RSi);printf("n");printf("关键字参加的比较次数：d,关键字的移动次数：dn",compare4,move4) printf("n");将两个有序序列归并为一个有序序列void Merge(int RS,int low,int mid,int high)/int i,j,k;int n1,n2;i=low;j=mid+1;k=low;while(i<=mid&&j<=high)/ 两两比较if(RSi<=RSj)Dk=RSi;i+;k+;elseDk=RSj;j+;k+;)compare5+;move5+;)if(i<=mid)for(n1=k,n2=i;n1<=high&&n2<=mid;n1+,n2+)(Dn1=RSn2;move5+;)elsefor(n1=k,n2=j;n1<=high&&n2<=high;n1+,n2+)(Dn1=RSn2;move5+;)for(mid=low;mid<=high;m