数据结构课程设计十种排序算法比较

1、合肥学院计算机科学与技术系课程设计报告2014 2015 学年第 学期课程 数据结构与算法课程设计名称内部排序算法比较学生姓名学号专业班级指导教师 2015 年 1 月【课题22、】内部排序算法比较一、问题分析和任务定义各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。根据对本设计任务要求的理解和分析，按以下两点问题进行分析：题目要求对十种排序算法进行比较，比较的主要内容是关键字的比较次数和移动次数，其中待排序数用。二、数据结构的选择和概要设计为了实现十种排序算法，产生的随机数用顺序表存储比

2、较方便。顺序表数据类型（存储结构）描述如下：typedef int KeyType; struct rec KeyType key;typedef rec sqlistN;2.主程序与各模块之间的关系是：(1) void gensort(int b,int n)起泡排序(2) void insertsort(sqlist b,int n)插入排序(3) void so(sqlist num,int n)折半插入排序(4) void shellsort(sqlist b,int n)希尔排序(5) void gentsort(int b,int n)选择排序(6) void output(sql

3、ist b,int n)快速排序(7) void sort3(sqlist nu,int n) /2-路插入排序(8) void Merge(sqlist a, sqlist b, int low, int mid, int high)二路归并排序(9) void MergePass(sqlist a, sqlist b, int n, int lenth)一趟归并排序(10) void MergeSort(sqlist a, int n) /进行二路归并(11) void sift(sqlist r,int s,int m) 堆排序(12) void init(int a)/随机生成N个整数

4、三、详细设计和编码在整个课程设计中，要求实现要求的功能，必须要有主函数，并通过主函数调用各功能子模块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。1.起泡排序函数的实现函数声明：void gensort(int b,int n)起泡排序的基本思想是将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。起泡排序是一种稳定的排序方法，在随机产生数的情况下，总的时间复杂度为O(n2)。2. 选择排序函数的实现函数声明：void gentsort(in

5、t b,int n)选择排序法的基本思想是：第i趟排序通过n-i次关键码的比较，在n-1+i (1 <= i <= n-1)个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。选择排序是一种稳定的排序方法，总的时间复杂度是O(n2)。3. 插入排序函数的实现函数声明：void insertsort(sqlist b,int n)直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到排好序的有序表中，直到无序区中没有记录为止，从而得到一个新的有序表。直接插入排序是一种稳定的排序方法，其时间复杂度为O(n)。4. 希尔排序函数的实现函数声明：void

6、shellsort(sqlist b,int n)希尔排序又称增量缩小排序，基本思想是先将序列按增量划分为元素个数相同的若干子序列，在子序列内分别进行直接插入排序，然后不断缩小增量直至为1，最后使用直接插入排序法完成排序。5. 折半插入排序函数的实现函数声明：void Dichotomy(int a,int n)；二分排序法的基本思想是：在插入第i个元素时，对前面的0(i-1)个元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半元素进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。 6. 快

7、速排序函数的实现函数声明：void output(sqlist b,int n)/输出元素值首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。快速排序是一种不稳定的排序方法，时间复杂度为O（nlog2n）7. 堆排序函数的实现函数声明：void sift(sqlist r,int s,int m)首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它们从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这

8、样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。堆排序是一种不稳定的排序方法，总的时间复杂度为O(nlog2n)。8.二路归并排序函数的实现函数声明：void Merge(sqlist a, sqlist b, int low, int mid, int high)void MergePass(sqlist a, sqlist b, int n, int lenth)void MergeSort(sqlist a, int n)合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n1r分成两个数组n1r/2与nr/2+1

9、r，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。9.2-路插入函数的实现9.2-路插入排序是在折半插入排序的基础上发展。其目的是减少排序过程中记录移动的次数，但为此需要n个记录的辅助空间。具体做法是：另设一个和L.r同类型的数组d，首先将L.r1赋值给的d1,将d1看成是排好序的序列中处与中间位置的记录，然后从L.r中第2个记录起依次插入到的d1之前或之后的有序序列中。先将待排序记录的关键

10、字和d1的关键字比较，若L.ri.key<d1.key,则将L.ri插入到d1之前的有序表中。反之，将L.ri插入到di之后的有序表中。在实现算法时，将d看成一个循环向量，并将两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。四、上机调试过程测试结果:2 结果分析实验结果与我们对这十种种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。实验结果还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序时间方面。七、参考文献1 王昆

11、仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。2 王立柱，C语言与数据结构.北京：清华大学出版社，2003年6月第1版。八、附录以上是对本设计的实现功能和算法等的全面分析，以下是带注释的源代码算法#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#define N 100int p,q;int g=0;int h=0;/起泡排序void gensort(int b,int n)int

12、i,j;int s=0,t=0;for(i=0;i<n-1;i+) for(j=i+1;j<n;j+) t+; if(bi>bj) int temp=bi; bi=bj; bj=temp; s+=3; cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;/插入排序typedef int KeyType; struct rec KeyType key;typedef rec sqlistN;void insertsort

13、(sqlist b,int n)int i,j;int s=0,t=0;for(i=2;i<n;i+) b0.key=bi.key; s+; j=i-1; t+; while(b0.key<bj.key) bj+1=bj; j-; s+; t+; bj+1=b0; s+; cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;/折半插入排序void so(sqlist num,int n)int s=0; int low,hi

14、gh,m;/分别指向低、高、中的位置 int i,j,k=0,t;/i,j循环 k交换次数 t哨兵 for(i=1;i<n;i+) t=numi.key ; low=0;high=i-1; while(low<=high) m=(low+high)/2; if(t<numm.key) high=m-1; k+; else low=m+1; for(j=i-1;j>=high+1;j-) numj+1.key=numj.key;s+; numhigh+1.key=t; cout<<"移动次数="<<s<<"

15、,"<<"比较次数="<<k<<endl;/希尔排序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<n;i+) j=i-gap; while(j>0) t+; if(bj.key>bj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap; s+=3; else j=0; gap=gap/2; cout<<"移动次

16、数="<<s<<","<<"比较次数="<<t<<endl;/选择排序 void gentsort(int b,int n)int i,j,k;int s=0,t=0;for(i=0;i<n-1;i+) k=i; for(j=i+1;j<n;j+) t+; if(bk>bj) k=j; if(k!=i) int temp=bk; bk=bi; bi=temp; s+=3; cout<<"移动次数="<<s<<&q

17、uot;,"<<"比较次数="<<t<<endl;/快速排序void output(sqlist b,int n)/输出元素值for(int i=0;i<n;i+) cout<<setw(4)<<bi.key;cout<<endl;void display(int n,int m)/输出计数cout<<"移动次数="<<n<<","<<"比较次数="<<m<<

18、;endl;void BeforeSort()/初始化计数器p=0;q=0;void quicksort(sqlist r,int s,int t)int i=s,j=t;if(s<t) r0=rs;p+; while(i<j) p+; while(i<j&&rj.key>=r0.key) j-; ri=rj; q+; p+; p+; while(i<j&&ri.key<=r0.key) i+; rj=ri;q+;p+; ri=r0;p+; else return;quicksort(r,s,j-1);quicksort(r,

19、j+1,t); void sort(sqlist r,int s,int t)BeforeSort();quicksort(r,s,t);display(p,q);/2-路插入排序void sort3(sqlist nu,int n)/int max=n;#define max 20 int first,final;/头尾指针 int cachemax+1;/中转站 int i,j,s=0;/i,j循环变量 k计数器int t=0; for(i=0;i<n;i+) if(0=i) first=0; final=0; cache0=nu0.key; else if(nui.key>=

20、cachefinal) t+; final+; cachefinal=nui.key; s+; else if(nui.key<=cachefirst) t+; if(first=0)first=n; first-; cachefirst=nui.key; s+; else t+; for(j=first;nui.key>cachej;) if(0=j) cachen-1=cache0; else cachej-1=cachej; s+;j+; if(j=n)j=0; if(0=first)first=n-1; else first-; if(0=j)j=n; cachej-1=n

21、ui.key; s+; for(i=first,j=0;j<n;j+) nuj.key=cachei; i+; if(i=n)i=0; cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;/二路归并void Merge(sqlist a, sqlist b, int low, int mid, int high)int i= low, j = mid + 1,k = low;while (i <= mid) &&am

22、p; (j <= high)if(ai.key <= aj.key) h+;bk+ = ai+;g+;+i;else h+;bk+ = aj+; g+;+j;+k;/if(i <= mid)while(i <= mid)bk+ = ai+;g+;/else while(j <= high)bk+=aj+;g+;/进行一趟归并void MergePass(sqlist a, sqlist b, int n, int lenth)int i = 0, k=0;while(i <= n - 2*lenth)Merge(a, b, i, i + lenth -1,

23、i + 2*lenth -1);i += 2*lenth;if(i < n - lenth ) Merge(a, b, i, i + lenth -1, n-1);else for(k = i; k <= n-1; k+)bk = ak;g+;/进行二路归并void MergeSort(sqlist a, int n)sqlist b;/int* b=(int*)malloc(n*sizeof(int);int lenth = 1;while(lenth < n/2+1) MergePass(a, b,n, lenth);lenth = 2*lenth;MergePass(b

24、, a, n, lenth);lenth = 2*lenth;cout<<"移动次数="<<g<<","<<"比较次数="<<h<<endl;/堆排序void sift(sqlist r,int s,int m)int j;rec x;x=rs;for(j=2*s;j<=m;j*=2)q+;if(j<m&&(rj.key<rj+1.key) +j;q+;if(!(x.key<rj.key) break;rs=rj;s=j;p

25、+;rs=x;p+;void heapsort(sqlist &r,int m)int i;rec w;for(i=m/2;i>0;-i) sift(r,i,m);for(i=m;i>1;-i) w=ri;ri=r1; r1=w; p+=3; sift(r,1,i-1);void sorting(sqlist &r,int t)BeforeSort();heapsort(r,t);display(p,q);void init(int a)/随机生成N个整数并 int i;/#define N 100; srand ( ( unsigned int ) time ( NULL ) ); for(i=0;i<N;i+) ai=rand()