排序算法比较数据结构课程报告.doc
《排序算法比较数据结构课程报告.doc》由会员分享,可在线阅读,更多相关《排序算法比较数据结构课程报告.doc(17页珍藏版)》请在沃文网上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 算法 比较 数据结构 课程 报告