归并排序实验报告

1、int i=s; int j=m+1; if(i<=m)while(i<=m) if(ri<=rj)r1k+=ri+;/r1k+=rj+; else while(j<=t) r1k+=rj+;/ for(int l=0;l<k;l+) rl=r1l;/if(s=t)r1s=rs;elseint m; m=(s+t)/2;第二个没处理完，进行收尾将合并完成后的 r1 序列送回 r 中 mergesort(r,r1,s,m);/ 归并排序前半个子篇一：归并排序与快速排序实验报告一、实验内容： 对二路归并排序和快速排序对于逆序的顺

2、序数的排序时间复杂度比较。二、所用算法的基本思想及复杂度分析：1、归并排序1) 基本思想：运用分治法，其分治策略为： 划分：将待排序列r1,r2, ” ,rn划分为两个长度相等的子序列r1, ,rn/2 和 rn/2+1, , ,rn 。 求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。 合并：将这两个有序子序列合并成一个有序子序列。2) 复杂度分析：二路归并排序的时间代价是 o(nlog2n) 。二路归并排序在合并过程中需要与原始记录序列同 样数量的存储空间，因此其空间复杂性 o(n) 。2、快速排序：1 ) 基本思想：运用分治法，其分治策略为： 划分：选定一个记录作为轴值，以轴

3、值为基准将整个序列划分为两个子序列r1 , ri-1和ri+1 , rn，轴值的位置i在划分的过程中确定，并且前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值。 求解子问题：分别对划分后的每一个子序列递归处理。 合并：由于对子序列r1 , ri-1和ri+1 , rn的排序是就地进行的，所以合并不需要执行任何操作。2) 复杂度分析：快速排序在平均时间复杂性是o(nlog2n)。最坏的情况下是 o(nA2)。三、源程序及注释：1 、 归并排序#include<iostream>#include<fstream>

4、#include windows.h using namespace std;void merge(int r,int r1,int s,int m,int t )int mergesort(int r,int r1,int s,int t)void main()int k=s; while(i<=m&&j<=t)r1k+=ri+;/ 第 一 个 没 处 理 完 ， 进 行 收 尾 取 ri 和 rj 中 较 小 的 放 入 r1k 中 else序列 mergesort(r,r1,m+1,t); /归并排序后半个子序列 merge(r

5、1,r,s,m,t);/ 合并两个已排序的子序列 return 0;int a100000; int a110000;int n,i;产生 3 个数组。int b3= 1000,3000,5000;/ for(int j=0; j<3; j+)n=bj;for(i=1; i<=n; i+) ai=n;large_integer begaintime ;large_integer endtime ;large_integer frequency;queryperformancefrequency(&frequency);queryperformance

6、counter(&amp ;begaintime) ;int c=mergesort(a,a1,0,n-1); queryperformancecounter(&endtime); cout << 数 据 个 数 为 <<n<<时 归 并 排 序 的 时 间 为 ( 单 位 ： s )：<<(double)( endtime1.quadpart - begaintime1.quadpart )/ frequency1.quadpart <&

7、;lt;endl;2、快速排序#include<iostream> #include<fstream>#include windows.husing namespace std;int partition (int data,int first,int end)int i,j; while(i<j) return i; while(i<j&&datai<=dataj)j-;/从左侧扫描 if(i<j) while(i<j&

8、&datai<=dataj)i+;/ 从右侧扫描 if(i<j) int temp1; temp1=datai; datai=dataj; dataj=temp1; /将较小的放到后面 j-; int temp; temp=datai; datai=dataj; dataj=temp;/将较小的放到前面 i+;int quicksort(int c,int first,int end)int i; if(first<end) i=partition(c,first,end);/对 chs 到 cht 进行一次划分 quicksort(c

9、,i+1,end);/ 递归处理右区间 return 0;void main()int a100000,n,i;int b3= 1000,3000,5000;/3 个数据范围for(int j=0; j<3; j+)n=bj;for(i=1; i<=n; i+) ai=n;large_integer begaintime ;large_integer endtime;large_integer frequency ;queryperformancefrequency(&frequency);queryperformancecounter(&a

10、mp;begaintime) ;int c= quicksort(a,0,n);queryperformancecounter(&endtime);cout << 数 据 个 数 为 <<n<<时 快 速 排 序 的 时 间 为 ( 单 位 ： s )：<<(double)( endtime.quadpart - begaintime.quadpart )/ frequency.quadpart <<endl;四、运行输出结果： 归并排序篇

11、二：算法分析与设计实验报告 - 合并排序、快速排序 实验报告实验一合并排序、快速排序一实验目的( 1) 学习合并排序和快速排序算法的思想，掌握原理。( 2) 运用合并排序和快速排序算法的思想进行编程实现，以加深理解。 二实验内容(1)输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。 ( 2)输入 10 个整数，运用快速排序的思想进行编程实现，输出正确的排序结果 三实验代码(1) 合并排序源代码如下：#include <iomanip.h>/ 调用 setw#include <iostream.h> / 将 b0 至 br

12、ight-left+1 拷贝到 aleft 至 aright template <class t>void copy(t a,t b,int left,int right) int size=right-left+1;for(int i=0;i<size;i+)aleft+=bi; / 合并有序数组 aleft:i,ai+1:right 到 b, 得到新的有序数组 b template <class t>void merge(t a,t b,int left,int i,int right) int a1cout=left,

13、/ 指向第一个数组开头 a1end=i,/ 指向第一个数组结尾 a2cout=i+1,/ 指向第二个数组开头 a2end=right,/ 指向第二个数组结尾 bcout=0;/ 指向 b 中的元素for(int j=0;j<right-left+1;j+)/ 执行 right-left+1 次循环 if(a1cout>a1end) bbcout+=aa2cout+;continue; / 如果第一个数组结束，拷贝第二个数组的元素到 b if(a2cout>a2end) bbcout+=aa1cout+;continue; / 如 果 第 二 个 数 组

14、 结 束 ， 拷 贝 第 一 个 数 组 的 元 素 到 b if(aa1cout<aa2cout) bbcout+=aa1cout+;continue; / 如果两个数组都没结束，比较元素大小，把较小的放入 belse bbcout+=aa2cout+;continue; /对数组 aleft:right 进行合并排序 template <class t>void mergesort(t a,int left,int right) t *b=new intright-left+1;if(left<right)int i=(left+ri

15、ght)/2;/ 取中点mergesort(a,left,i);/ 左半边进行合并排序 mergesort(a,i+1,right);/ 右半边进行合并 排序 merge(a,b,left,i,right);/ 左右合并到 b 中copy(a,b,left,right);/ 从 b 拷贝回来int main() int n;cout<< 请输入您将要排序的数目 :; cin>>n; int *a=new intn; cout<< 请输入相应的数字： ;for(int i=0;i<n;i+) cin

16、>>ai; mergesort( a, 0, n-1); cout<< 排序结果 :; for(int j=0;j<n;j+) cout<<setw(5)<<aj; cout<<endl;return 1;(2)快速排序源代码如下：#include <iostream.h>#define max 10int quicksort(int a,int l,int r)int pivot; / 枢轴int i=l;int

17、 j=r;int tmp; pivot=a(l+r)/2;/ 取数组中间的数为枢轴 do while (ai<pivot) i+; /i 右移 while (aj>pivot) j-;/ j左移if (i<=j)tmp=ai;ai=aj;aj=tmp; / 交换 ai 和 aj i+;j-; while(i<=j);if (l<j) quicksort(a,l,j);if (i<r) quicksort(a,i,r);return 1;int main()int arraymax;int i;cout&

18、lt;< 请输入 <<max<< 个整数 :; for (i=0;i<max;i+) cin>>arrayi;quicksort(array,0,max-1); cout<< 快 速 排 序 后 ： <<endl; for (i=0;i<max;i+)cout<<arrayi<< ; cout<<endl;return 0; 四实验

19、结果五总结与思考篇三：合并、快速排序实验报告 合并、快速排序 一实验目的：1. 理解算法设计的基本步骤及各部的主要内容、基本要求；2. 加深对分治设计方法基本思想的理解， 并利用其解决现实生活中的问题； 3. 通过本次试 验初步掌握将算法转化为计算机上机程序的方法。 二实验内容：1. 设计和实现递归的合并排序算法、 快速排序算法； 2. 设计和实现消除递归的合并排序算 法、快速排序算法；3. 设计有代表性的典型输入数据，分析算法的效率；4. 对于给定的输入数据， 给出算运行结果和运行结果， 并给出实验结果分。 三实验操作：1. 合并排序思想： 归并排序是建立在归并操作上的一种有效的排序算法。该

20、算法是采用分治法的思想，是一种 稳定的排序方法。将以有序的子序列合并，得到完全有序的序列；及先使每个字序列有序， 再使子序列段间有序。归并过程：比较数组中两个元素的大小，如比较 ai 和 aj 的大小，若 ai<=aj ， 将第一个有序表中的元素 ai 复制到 rk 中，并令 i 和 k 分别加上 1，如此循环下去，直到 其中一个有序表取完，然后再将另一个有序表剩下的元素复制到 r 中从下标 k 到下标 t 的单 元。如： 6 ， 202，100， 301， 38， 8，1第一次归并： 6 ，202 ，100 ，301 ，8 ，38 ，1 第二次归并： 6 ，100，202，30

21、1 ，1， 8，38 第三次归并： 1 ，6，8，38，100，202，301 合并排序算法： void merge(int array,int low,int high)int i=low,j,k;int mid=(low+high)/2; j=mid+1; k=low;int* list=new inthigh+1; while(i<=mid&&j<=high) if(arrayi<=arrayj) listk+=arrayi+;else listk+=arrayj+; while(i<=mid) li

22、stk+=arrayi+; while(j<=high) listk+=arrayj+; for(int n=low;n<=high;n+)arrayn=listn;void mergesort(int array,int low,int high)if(low<high)int mid=(low+high)/2;mergesort(array,low,mid);mergesort(array,mid+1,high); merge(array,low,high); 2. 快速排序思想：将要排序的数据存入数组中，首先任意去一个元素（通常选用数组的第一个数

23、）作为关键数 据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，值得注意的是， 快速排序不是一种稳定的排序算法，即多个相同的值的相对位置也许会在算法结束时产生变 动。快速排序的过程：1） 设置两个变量 i,j ，排序开始的时候： i=0,j=n-1 （ n 为元素个数） ； 2 ） 以第一个数组 元素作为关键数据，赋给key，即key=aO ; 3 ）从j开始向前搜索，即由后开始向前搜索（j- ），找到第一个小于 key的值 aj ，将 aj 和 ai 互换;4） 从 i 开始向后搜索，即由前开始向后搜索（ i+ ），找到第一个大于 key的 ai ，将 ai 和 aj 互换;

24、 5） 重复第 3、4 步，直到 i=j ; 如：快速排序的算法：void qsort(int list,intlow,int high) if(low>=high)return; int first=low; intlast=high;-last;+first;int key=listfirst; while(first<last) while(first<last&&listlast>=key) listfirst=listlast;while(first<last&&am

25、p;amp;listfirst<=key) listlast=listfirst; listfirst=key;qsort(list,low,first-1); qsort(list,last+1,high);3. 实验数据的输入：Cin 流输入来控制数据的输入。本实验采用将数据输入与输出存储到文件中的方式，需要采用C+文件流操作，对于数据的输入，由于 cin 对数据的读取会忽略空格和换行操作，使用 对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数 据存入到另一文件之中。由于输入需要大量的数据，可采用从“随机数 .txt ”中读取数据。 文件输入算

26、法：int input()ofstream outfile;outfile.open(e:/ 程 序 设 计 /praCtiCe 1/ 算 法 设 计 与 分 析 文 本 文 件 夹 /number2.txt,ios:trunC);if(!outfile.is_open() Cout<<file Cant open!<<endl;Cout<<input numbers:<<endl;Char num;int length=0;Cin.get(num);while(num!=e) length+; outfile<<num;Cin.get(num); outfile.Close(); return length;文件输出算法：void output(int length) double start,end; ifstream infile; ofstream outfile;infile.open(e:/ 程序设计 /practice 1/ 算法设计与分析 / 文本文件夹 /number2.txt);outfil