排序问题的二分排序和归并排序.docx

《排序问题的二分排序和归并排序.docx》由会员分享，可在线阅读，更多相关《排序问题的二分排序和归并排序.docx（6页珍藏版）》请在三一办公上搜索。

1、1.实验目的（结出本次实验所涉及并要求掌握的知识点）快速排序和归并排序两个算法学习分而治之策略并分析递归函数的时间复杂度2.实验内容（结出实验内容具体描述）快速排序和归并排序都是使用分而治之策略开发的求解排序问题的算法（1）分别实现这两个算法（2）从分而治之策略的几个步骤分析他们的区别（3）将主要步骤的时间复杂度以注释形式插入在程序代码中。3 .算法描述及实验步骤（用适当的形式表达算法设计思想与算法实现步骤）1.快速排序void quickSort(int left,int right,int a) / T(n)=2T(n/2)+O(n) if(left=right)return;elsein

2、t i=left;int j=right;int temp=aleft;int flag=1;while(j!=i)while(flag & j!=i) if(ajtemp)flag=1;aj=ai; elsei+；ai=temp;quickSort(left,i-1,a);quickSort(i+1,right,a);/ divide (以i为左右边界)/ T(n/2)/ T(n/2)2.归并排序void merge(int arr,int left,int mid,int right) / O(n)int m=mid-left;int end=right-left;int copyend+

3、1;int i,j,k;for(i=0,j=left;i=end;i+,j+) / O(n)copyi=arrj;i=0;j=m+1;k=left;while(i=m & j=end)/O(n)if(copyim)/O(n)for(;j=end;j+,k+)arrk=copyj;elsefor(;i=m;i+,k+)arrk=copyi;_void mergeSort(int arr,int left,int right) / T(n)=2T(n/2)+O(n)if(left=right)/ basic casereturn;else/ recursive caseint mid=(left+

4、right)/2; / divide mergeSort(arr,left,mid); / T(n/2) mergeSort(arr,mid+1,right); / T(n/2) merge(arr,left,mid,right); / combine: O(n) 4.调试过程及运行结果(详细记录在调试过程中出现的问题及解决方法。记录实验执行 的结果)右边是归并排序左边是快速排序请输入数组古小n:8请输入数组大小n:8请输入数组元素:请输入数据：9 4 1 -4011 -30L909 4 1 01 -30190快速排序后的数组：归并排序后的数组，-30 -4 014 9 11L90-30 -4

5、 014 9 11190Process returned0(0x0)executiontime : 511 sprocessreturned0(0x0)executiontime : 1, 564 s*S.B=_!a.测试数据二:测试数据三:测试数据四:商输入数据快速拌序后的数组归并排序后的数组Process returnedexecution timeToc&ss returned清输入数组大小 请输入数组元谖execution tine测试数据五:5.总结（对实验结果进行分析，问题回答，实验心得体会及改进意见）在使用分而治之策略解决问题时候，要考虑：把原问题分解成规模较小的子问题后，在 子

6、问题容易求解的情况下，能否利用其结果使原问题得到解决。主要步骤有：Divide：将原问题分解Conquer :解决子问题Combine :利用子问题的解，解决原问题（不是必须，有时候子问题解决的同时原问题 也解决了）6 .附录（程序源代码等）#include #include void quickSort(int left,int right,int a)if(left=right)return;/ basic case: O(1)else/ recursive caseint i=left;int j=right;/ conquerint temp=aleft;/ O(n)int flag=

7、1;while(j!=i)while(flag & j!=i) if(ajtemp)flag=1;aj=ai; elsei+；ai=temp;quickSort(left,i-1,a);quickSort(i+1,right,a);/ divide (以i为左右边界)/ T(n/2)/ T(n/2)int main()int n;printf(请输入数组大小n:);scanf(%d,&n);int an;printf(-请输入数组元素：)；for(int i=0;in;i+) scanf(%d,&ai);quickSort(0,n-1,a);for(int i=0;in;i+) printf(

8、%d ,ai);return 0;#include #include void merge(int arr,int left,int mid,int right) / O(n)int m=mid-left;int end=right-left;int copyend+1;int i,j,k;for(i=0,j=left;i=end;i+,j+) / O(n) copyi=arrj; i=0; j=m+1; k=left; while(i=m & j=end)/O(n)if(copyim)/O(n)for(;j=end;j+,k+) arrk=copyj; else for(;i=m;i+,k+

9、) arrk=copyi; void mergeSort(int arr,int left,int right) / T(n)=2T(n/2)+O(n) if(left=right) return;else int mid=(left+right)/2; / divide mergeSort(arr,left,mid); / T(n/2) mergeSort(arr,mid+1,right); / T(n/2) merge(arr,left,mid,right); / combine O(n) int main() int i=0;int n;printf(请输入数组大小n:);scanf(%d”,&n);int arrn;printf(请输入数据:nt);for(;in;i+)scanf(%d”,&arri)；mergeSort(arr,0,n-1);printf(归并排序后的数组：nt);for(i=0;in;i+)printf(%d ,arri);return 0;