排序算法的实现与对比

1、实 验 报 告（三）课程名称： 软件技术基础 实验题目：排序算法的实现与对比 系 别： 仪器科学与光电工程学院 专 业： 光信息科学与技术 班 级： 光信1102 学 号： 2011010739 姓 名： 郭世栋 指导教师： 刘力双 实验日期： 201305 实验三 、排序算法的实现与对比1.实验目的：掌握排序方法，并使用C语言实现排序算法，理解排序的定义和种类排序的特点，了解排序过程以及依据的原则，并了解各种排序方法的时间复杂度分析，掌握一种计时方法。2.实验内容：(1)分别编写函数进行冒泡排序、简单插入排序、简单选择排序、快速排序(2)编制一个应用程序，它将随机产生的N个整数插入到一个顺序

2、表中，然后分别用哪个上述排序算法对这个顺序进行排序；记录并显示各种方法的运行时间；(3)以N=5000和N=50000运行这个程序，对算法运行的时间作比较分析；3.实验步骤：产生随机数代码#include #include #include int main(void)srand (unsigned )time (NULL);int i,a10; printf(产生的随机数为：);for (i=0;i=9;i+) ai=rand();printf(%d ,ai);printf(n);如果感觉随机数过大可以规定其在百以内即将代码ai=rand();改为ai=rand()%100+1;如图：进行随

3、机数排序时对同一组随机数进行多种排序#include#define M 100000#include typedef int ElemType;/直接插入排序void InsertSort ( ElemType A, int n )int i, j;ElemType x;for(i=1;i=0;j-) if (xAj) Aj+1=Aj; else break; Aj+1=x; /直接选择排序void SelectSort(ElemType A, int n) int i, j, k; ElemType x; for ( i=0; i=n-2; i+ ) k=i; for(j=i+1;j=n-1

4、;j+) if(AjAk)k=j; if(k!=i) x=Ai; Ai=Ak; Ak=x; /冒泡排序void BubbleSort( ElemType B, int n )int i, j, flag; ElemType x;for (i=1; i=i; j-) if ( Bj Bj-1) flag=1; x=Bj; Bj=Bj-1; Bj-1=x; if (flag=0) break;/快速排序void QuickSort(int A,int s,int t) int i,j,temp,k; i=s; j=t; k=A(s+t)/2; do while(Aik&ik&js) j-; if(

5、i=j) temp=Ai; Ai=Aj; Aj=temp; i+; j-; while(i=j);if(is) QuickSort(A,s,j);void main() int i,N,AM,BM;coutN; cout产生的随机数为：;for(i=0;iN;i+)Ai=rand()%100+1;for(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)coutAi ;coutnendl;cout直接插入排序endl;InsertSort (A, N ); cout直接选择排序endl;SelectSort(A, N ); cout冒泡排序endl; BubbleSort(B, N

6、); cout快速排序endl;QuickSort(A,1,N-1); cout排好后的顺序为;for(i=0;iN;i+)coutAi ;coutn; 当排序代码编号后对各排序进行计时此步骤出现的问题很多初代码#include#include #define M 100000#include double time1,time2,time3,time4;clock_t start,end;typedef int ElemType;/直接插入排序void InsertSort ( ElemType A, int n )int i, j;ElemType x; start=clock();for

7、( i=1; i=0; j- ) if ( x Aj ) Aj+1=Aj; else break; Aj+1=x; end=clock();time1=(double)(end-start);couttime1毫秒endl;/直接选择排序void SelectSort(ElemType A, int n) int i, j, k; ElemType x; start=clock(); for ( i=0; i=n-2; i+ ) k=i; for(j=i+1; j=n-1; j+) if (AjAk) k=j; if (k!=i) x=Ai; Ai=Ak; Ak=x; end=clock();

8、 time2=(double)(end-start); couttime2毫秒endl;/冒泡排序void BubbleSort( ElemType B, int n )int i, j, flag; start=clock();ElemType x;for (i=1; i=i;j-) if(BjBj-1) flag=1; x=Bj;Bj=Bj-1;Bj-1=x; if (flag=0) break; end=clock();time3=(double)(end-start);couttime3毫秒endl;/快速排序void QuickSort(int B,int s,int t) int

9、i,j,temp,k; i=s; j=t; k=B(s+t)/2; start=clock(); do while(Bik&ik&js) j-; if(i=j) temp=Bi; Bi=Bj; Bj=temp; i+; j-; while(i=j); if(is) QuickSort(B,s,j); end=clock(); time4=(double)(end-start); couttime4毫秒endl;void main() int i,N,AM,BM;coutN; srand(unsigned)time(NULL);for(i=0;iN;i+) Ai=rand();for(i=0;i

10、N;i+)Bi=Ai;coutnendl;cout直接插入排序，所用时间为endl;InsertSort (A, N );cout直接选择排序:endl;SelectSort(A, N ); cout冒泡排序:endl; BubbleSort(B, N ); cout快速排序:endl;QuickSort(B,0,1); 当编写好代码后我分别对N进行取值5000和50000发现快速排序无论何时都是零毫秒，这是不可能的，速度再快也不可能连一毫秒都用不了。我针对快速排序的部分代码进行分析。请教老师，老师说可能是由于我用的数组都是AN可能在执行上一个排序时已经将顺序排好因此在执行快速排序时直接停止。

11、于是我在左下图所示处添加了新数组QN,把AN的值分别赋给QN,同BN一样。并将快速排序中的所有有关AN项全部替换成QN。并期待着成功，但是更大的问题出现了。改后void main()部分代码 改后快速排序部分代码 加入时间代码后执行，此时出现了从来没遇到过的问题如图：屏幕上居然什么都没了，当时一下子震惊了。我仅仅只是多添加了一个数组，情况和预期向着反方向进行了。突然想起第一次实验的断点调试知识于是在快速排序出设立了断点，然后按F5进行调试。问题的根源Stack Overflow？上网查了一下，发现原来是叫“栈堆溢出”，看来是我定义的数组占用的栈值过长导致系统数据v被覆盖，造成无法显示。找到了解

12、决办法，如下：在“工程”标签处选择设置，单击“连接”，在下面有个滚动条，选择“输出”修改保留值为01000000(即是将默认的栈长度1M改为10M)然后再次执行发现可以执行但是快速排序时间还是零最后的情况就可能是时间函数start=clock()位置放错，于是我将快速排序中的start=clock()和end=clock()转移到了void main()部分中调用快速排序函数中，并将QuickSort(Q,0,1)改为了QuickSort(Q,1,N-1)改后的代码为左图。再次执行程序后发现快速排序时间正常显示了。我又突发奇想，把前面三个排序代码的时间函数都移到最后的void main当中去，

13、但发现除了快速排序正常显示时间以外其他的排序都为零了，可见这种解决办法仅仅适用于快速排序，其他排序只能按照最初的方法进行计时。改正后全代码#include#include #define M 100000#include double time1,time2,time3,time4;clock_t start,end;typedef int ElemType;void InsertSort ( ElemType A, int n )/直接插入排序int i, j;ElemType x; start=clock();for( i=1; i=0; j- ) if ( x Aj ) Aj+1=Aj;

14、 else break; Aj+1=x; end=clock();time1=(double)(end-start);couttime1毫秒endl;void SelectSort(ElemType A, int n)/直接选择排序 int i, j, k; ElemType x; start=clock(); for ( i=0; i=n-2; i+ ) k=i; for(j=i+1; j=n-1; j+) if(AjAk)k=j; if(k!=i) x=Ai;Ai=Ak;Ak=x; end=clock(); time2=(double)(end-start); couttime2毫秒end

15、l;void BubbleSort( ElemType B, int n )/冒泡排序int i,j,flag; start=clock();ElemType x;for (i=1; i=i;j-) if(BjBj-1) flag=1; x=Bj;Bj=Bj-1;Bj-1=x; if(flag=0)break;end=clock();time3=(double)(end-start);couttime3毫秒endl;void QuickSort(int Q,int s,int t)/快速排序 int i,j,temp,k; i=s;j=t; k=Q(s+t)/2; do while(Qik&i

16、k&js) j-; if(i=j) temp=Qi; Qi=Qj; Qj=temp; i+; j-; while(i=j);if(is) QuickSort(Q,s,j);void main() int i,N,AM,BM,QM;coutN; srand(unsigned) time(NULL);for(i=0;iN;i+) Ai=rand();for(i=0;iN;i+)Bi=Ai;Qi=Bi;coutnendl;cout直接插入排序，所用时间为endl;InsertSort (A, N );cout直接选择排序:endl;SelectSort(A, N ); cout冒泡排序:endl;

17、BubbleSort(B, N ); cout快速排序:endl;start=clock();QuickSort(Q,1,N-1);end=clock(); time4=(double)(end-start); couttime4毫秒endl; 执行后对N=5000和50000进行对比 比较N=5000和50000发现直接插入排序和直接选择排序所用时间相同，冒泡排序所用时间最长，快速排序所用时间最短。N=5000的时候插入为85ms，N=50000时插入为8117ms差100倍，同理选择和冒泡的N=50000均比N=5000多100倍时间，可见随机数越多，排序的时间复杂度将越复杂，并成很大趋势上涨。相对于前三个排序而言，快速排序的时间复杂度很小，N=5000时才用1ms还是约等于1ms，N=50000时才16ms，所用时间才是插入、选择的千分之二是冒泡排序的万分之七。可见随机数越是无顺序，对于快速排序来说时间复杂度越低，因此快速排序的排序方法是比较适用于大数组的排列。冒泡排序算法的时间复杂度最大，这和它比较的方法有关，冒泡排序基本思想是：从R1开始，两两比较相邻的记录的关键字，并按从小到大排列，因此在每一趟排列时都要进行两两比较，比较次数比其他的算法多，因此时间也最长。实验总结在此次实验中我们利用C+进行了随机数的插入、选择、冒泡