排序算法比较数据结构课程报告.doc

1、 目录 1、 需求分析说明- 32、 总体设计- 43、 详细设计- 54、 实现部分- 75、 程序测试- 176、 总结- 18一、需求分析说明排序算法用到了以下算法思想：1、直接插入排序 2、冒泡排序 3、快速排序 4、直接选择排序 5、堆排序 6、二路归并排序二、总体设计开始创建6个包含30000个元素的数组u、v、w、x、y、z。直接插入方法：insertsort(u);冒泡方法：bubblesort(v);快速方法：quicksort(w);直接选择方法：selectsort(x);堆方法：heapsort(y);结束二路归并方法：mergesort(z);三、详细设计1、直接插入

2、排序 ：insertsort()在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。 将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。 排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降

3、序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。2、冒泡排序：bubblesort()基本思想: 设待排序的文件为r1.n 第1趟(遍)：从r1开始,依次比较两个相邻记录的关键字ri.key和ri+1.key,若ri.keyri+1.key，则交换记录ri和ri+1的位置；否则,不交换。(i=1,2,.n-1) 第1趟之后,n个关键字中最大的记录移到了rn的位置上。第2趟：从r1开始,依次比较两个相邻记录的关键字ri.key和ri

4、+1.key,若ri.keyri+1.key，则交换记录ri和ri+1的位置；否则,不交换。 (i=1,2,.n-2) 第2趟之后,前n-1个关键字中最大的记录移到了rn-1的位置上，作完n-1趟,或者不需再交换记录时为止。3、快序排序：quicksort()基本思想：首先在r1.n中，确定一个ri，经过比较和移动，将ri放到中间某个位置上，使得ri左边所有记录的关键字小于等于ri.key，ri右边所有记录的关键字大于等于ri.key。以ri为界,将文件划分为左、右两个子文件。用同样的方法分别对这两个子文件进行划分, 得到4个更小的子文件。继续进行下去,使得每个子文件只有一个记录为止,便得到原

5、文件的有序文件。例. 给定文件(20,05,37,08,63,12,59,15,44,08)，选用第1个元素20进行划分: 4、直接选择排序：selectsort()每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从arrayk开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比arrayk-1更小的元素，则把arrayminlIndex和ak-1对调，这时arrayk到最后一个元素中最小的元素就换到了arrayk-

6、1的位置。 如此反复进行第二轮、第三轮直到循环至最后一元素5、堆排序：heapsort()堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。1、N（N1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。2、且对于编号 i（1=iN，则节点i没有左孩子，否则其左孩子为2i；若2i+1N，则没有右孩子，否则其右孩子为2i+1。3、这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。堆排序其实最主要的

7、两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后

8、再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。6、归并排序：mergesort() 假定文件(r1,r2,.,rn)中记录是随机排列的,进行二路归并排序，首先把它划分为长度均为1的n个有序子文件，然后对它们逐步进行2路归并排序。其步骤如下：第1趟：从r1.n中的第1个和第2个有序子文件开始,调用算法merge,每次归并两个相邻子文件,归并结果放到y1.n中。在y中形成 n/2 个长度为2的有序子文件。若n为奇数,则y中最后一个子文件的长度为1。 第2趟：把y1.n看作输入文件,将 n/2 个有序子文件两两归并,归并结果回送到r1.n中,在r中形成 n/2/2个长度为4的有序

9、子文件。若y中有奇数个子文件，则r中最后一个子文件的长度为2。共计经过 log2n 趟归并,最后得到n个记录的有序文件。四、实现部分/排序算法实现#include#include#include#include#include#define ElemType intusing namespace std;const int N=30000;double time1,time2,time3,time4,time5,time6;class Sortingpublic:void insertsort(ElemType R,int n); /直接插入法排序void bubblesort(ElemTyp

10、e R,int n); /起泡排序void quicksort(ElemType R,int left,int right); /快速排序void selectsort(ElemType R,int n); /直接选择排序void heapsort(ElemType R,int n); /堆排序void mergesort(ElemType R,int n); /二路归并排序void print_insertsort();void print_bubblesort();void print_quicksort();void print_selectsort();void print_heaps

11、ort();void print_mergesort();void print(ElemType R,int n); /输出元素void print_sort();private:void creatheap(ElemType R,int i,int n); /建立大根堆void mergepass(ElemType R,ElemType A,int n,int c);void merge(ElemType R,ElemType A,int s,int m,int t);void Sorting:insertsort(ElemType R,int n) /直接插入法排序for(int i=1;

12、i=0)&(tempRj)Rj+1=Rj; /顺序比较和移动j-;Rj+1=temp; void Sorting:bubblesort(ElemType R,int n)int flag=1; /当flag为0时则停止排序for(int i=1;i=i;j-)if(RjRj-1) /发生逆序ElemType t=Rj;Rj=Rj-1;Rj-1=t; flag=1; /交换，并标记发生了交换if(flag=0) break;void Sorting:quicksort(ElemType R,int left,int right)/快速排序 int i=left,j=right;ElemType

13、temp=Ri;while(ij)while(Rji)j=j-1;if(ji)Ri=Rj;i=i+1;while(Rii)i=i+1;if(ij)Rj=Ri;j=j-1; /一次划分得到基准值的正确位置Ri=temp;if(lefti-1) quicksort(R,left,i-1); /递归调用左子区间if(i+1right) quicksort(R,i+1,right); /递归调用右子区间void Sorting:selectsort(ElemType R,int n) /直接选择排序int i,j,m;ElemType t;for(i=0;in-1;i+)m=i;for(j=i+1;j

14、n;j+)if(RjRm) m=j;if(m!=i)t=Ri;Ri=Rm;Rm=t;void Sorting:creatheap(ElemType R,int i,int n) /建立大根堆int j;ElemType t;t=Ri;j=2*i;while(jn)if(jn)&(RjRj+1)j+;if(t=0;i-)creatheap(R,i,n);for(i=n-1;i=0;i-)t=R0;R0=Ri;Ri=t;creatheap(R,0,i-1);void Sorting:merge(ElemType R,ElemType A,int s,int m,int t) /将两个子区间RsRm

15、和Rm+1Rt合并，结果存入A中int i,j,k;i=s;j=m+1;k=s;while(i=m)&(j=t)if(Ri=Rj)Ak=Rj;i+; k+;elseAk=Rj;j+; k+;while(i=m) /复制第一个区间中剩下的元素Ak=Ri;i+; k+;while(j=t) /复制第二个区间中剩下的元素Ak=Rj;j+; k+;void Sorting:mergepass(ElemType R,ElemType A,int n,int c) /对R数组做一躺归并，结果存入A数组中，n为元素个数，c为区间长度int i,j;i=0;while(i+2*c-1=n-1) /长度均为c的

16、两个区间合并成一个区间merge(R,A,i,i+c-1,i+2*c-1);i=i+2*c;if(i+c-1n) /长度不等的两个区间合并成一个区间merge(R,A,i,i+c-1,n-1);elsefor(j=i;j=n-1;j+) /仅剩一个区间时直接复制到A中Aj=Rj;void Sorting:mergesort(ElemType R,int n) /归并排序int c=1;ElemType AN;while(cn)mergepass(R,A,n,c); /一次合并，结果存入A中c*=2; /区间长度扩大一倍mergepass(A,R,n,c); /再次合并，结果存入R中c*=2;v

17、oid Sorting:print_insertsort() cout排序算法名称为:直接插入排序! endl; cout时间复杂度o(N2)endl; cout数据量大小（多少个）为:Nendl; cout实际执行时间为:time1(毫秒)endl;void Sorting:print_bubblesort() cout排序算法名称为:冒泡排序! endl; cout时间复杂度O(N2)endl; cout数据量大小（多少个）为:Nendl; cout实际执行时间为:time2(毫秒)endl;void Sorting:print_quicksort() cout排序算法名称为:快速排序!

18、endl; cout时间复杂度o(N*log2(N)endl; cout数据量大小（多少个）为:Nendl; cout实际执行时间为:time3(毫秒)endl;void Sorting:print_selectsort() cout排序算法名称为:直接选择排序! endl; cout时间复杂度O(N2)endl; cout数据量大小（多少个）为:Nendl; cout实际执行时间为:time4(毫秒)endl;void Sorting:print_heapsort() cout排序算法名称为:堆排序! endl; cout时间复杂度O(Nlog2(N)endl; cout数据量大小（多少个）

19、为:Nendl; cout实际执行时间为:time5(毫秒)endl;void Sorting:print_mergesort() cout排序算法名称为: 二路归并排序! endl; cout时间复杂度O(N*log2(N)endl; cout数据量大小（多少个）为:Nendl; cout实际执行时间为:time6(毫秒)endl;void Sorting:print(ElemType R,int n)for(int i=0;in;i+)if(i%10=0)coutendl;coutRisetw(6);coutendl;void Sorting:print_sort() cout 排序算法名

20、称|t时间复杂度|t数据量|t 执行时间(毫秒)|endl; coutendl; cout 直接插入排序:tO(N2) tN ttime1endl; cout 冒泡排序: tO(N2) tN ttime2endl; cout 快速排序: tO(N*log2(N)tN ttime3endl; cout 直接选择排序:tO(N2) tN ttime4endl; cout 堆排序: tO(N*log2(N)tN ttime5endl; cout 二路归并排序:tO(N*log2(N)tN ttime6endl; coutendl;void main()int c1=0,c2=0,c3=0,c4=0,

21、c5=0,c6=0;/判断算法是否执行过int ch,x;Sorting S; /算法类 ElemType RN,TN;srand(time(0); /产生时间种子 for(int i=0;iN;i+)Ti=rand()%N+1; coutendl; coutendl; cout 欢 迎 进 入 内 排 序 比 较 系 统 endl; coutendl; cout随机生成的原数组为：endl; S.print(T,N); coutendl; do cout请选择排序方法或查看各种排序算法的性能比较!endl; cout 退出endl; cout 直接插入排序endl; cout 冒泡排序end

22、l; cout 快速排序endl; cout 直接选择排序endl; cout 堆排序endl; cout 二路归并排序endl; cout 查看各种排序算法的性能比较ch; switch(ch) case 1: if(c1=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.insertsort(R,N); finish=clock(); time1=finish-start; c1=1; S.print_insertsort(); break; case 2: if(c2=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.b

23、ubblesort(R,N); finish=clock(); time2=finish-start; c2=1; S.print_bubblesort(); break; case 3: if(c3=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.quicksort(R,0,N-1); finish=clock(); time3=finish-start; c3=1; S.print_quicksort(); break; case 4: if(c4=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.selectsort(

24、R,N); finish=clock(); time4=finish-start; c4=1; S.print_selectsort(); break; case 5: if(c5=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.heapsort(R,N); finish=clock(); time5=finish-start; c5=1; S.print_heapsort(); break; case 6: if(c6=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.mergesort(R,N); finish=cloc

25、k(); time6=finish-start; c6=1; S.print_mergesort(); break; case 7: if(c1=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.insertsort(R,N); finish=clock(); time1=finish-start; c1=1; if(c2=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.bubblesort(R,N); finish=clock(); time2=finish-start; c2=1; if(c3=0) for(i=0;iN

26、;i+) Ri=Ti; start=clock(); S.quicksort(R,0,N-1); finish=clock(); time3=finish-start; c3=1; if(c4=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.selectsort(R,N); finish=clock(); time4=finish-start; c4=1; if(c5=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.heapsort(R,N); finish=clock(); time5=finish-start; c5=

27、1; if(c6=0) for(i=0;iN;i+) Ri=Ti; start=clock(); S.mergesort(R,N); finish=clock(); time6=finish-start; c6=1; S.print_sort(); break; case 0: x=0; break; while(x); 五、程序测试六、总结做这次试验然自己在此认识了什么是面向对象语言和C+强大数据处理功能。这已是我第二次做C+课程设计时就觉得它。重新认识和更加认识面向对象的特点，尽管C+不是纯面向对象的语言，但他的功能却非常强大作用广泛。，现在真正要用它编程了，以前把C+当C来学是彻底的错了

28、，C+的这些机制对C来说是质的飞跃，类是数据更安全，数据与对应数据的特定的操作关系更紧密、多态性是编译器为程序员分担了很多工作，程序员再不必仅为不同的数据类型浪费精力写冗余的代码、错误处理机制使程序在出错时得到更适当的处理，而不是程序崩溃甚至是粗暴地结束程序。C+对现实的模拟比C进了一大步，对象很像现实世界的物体，代码易理解、易维护、易使用，而且安全性更好，一个没有错误和警告的C程序用C+编译器编译，可能会发现很多隐蔽的错误，这些错误在一定条件下可能会有灾难性后果，从这点就可以看出C+对C的提升。C+相比C的诸多优越之处，真的只有写过程序才会有体会，用了一年多的C，现在觉得还没有才接触不到一个

29、月的C+习惯，可见C+的易用性。 在这门课程中碰到了许多自己以前不了解的内容，对我特别深刻的就是“指针”的全新认识，以前“指针”对我来说就是陌生的，通过这门课我基本上认识和学会用“指针”用法。通过这次课程我碰到了许多不了解的排序问题，我以前只知道直接选择思想这种排法而且还不知道它就是选择排序，通过这次实验我了解了六种常见的排序算法，这几种排序算法各有各的特点和有点，所以在程序用这几种就做够得到满意的排序了，这对程序的效率提到有很多帮助。还有就是认识了几个库函数，最让我记忆犹新的是计算时间的函数，开始设计是用的是c语言的时间函数它的精确度让我不满意，然后我就选择了c+里的时间函数精确度到了毫秒，让我受益匪浅。尽管时间很紧，没时间。但还是感谢有这么一次课程设计。17