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

1.实验目的（结出本次实验所涉及并要求掌握的知识点）快速排序和归并排序两个算法学习分而治之策略并分析递归函数的时间复杂度2.实验内容（结出实验内容具体描述）快速排序和归并排序都是使用分而治之策略开发的求解排序问题的算法（1）分别实现这两个算法（2）从分而治之策略的几个步骤分析他们的区别（3）将主要步骤的时间复杂度以注释形式插入在程序代码中。3.算法描述及实验步骤（用适当的形式表达算法设计思想与算法实现步骤）1.快速排序voidquickSort(intleft,intright,inta[]){//T(n)=2T(n/2)+O(n)if(left>=right)return;else{inti=left;intj=right;inttemp=a[left];intflag=1;while(j!=i){while(flag&&j!=i){if(a[j]<=temp){flag=0;a[i]=a[j];}elsej--;//basiccase:O(1)//recursivecase//conquer//O(n)}while(flag==0&&j!=i){if(a[i]>temp){flag=1;a[j]=a[i];}elsei++；}}a[i]=temp;quickSort(left,i-1,a);quickSort(i+1,right,a);//divide(以i为左右边界)//T(n/2)//T(n/2)2.归并排序voidmerge(intarr[],intleft,intmid,intright){//O(n)intm=mid-left;intend=right-left;intcopy[end+1];inti,j,k;for(i=0,j=left;i<=end;i++,j++)//O(n)copy[i]=arr[j];i=0;j=m+1;k=left;while(i<=m&&j<=end){//O(n)if(copy[i]<copy[j]){arr[k]=copy[i];i++;}else{arr[k]=copy[j];j++;}k++;}if(i>m)//O(n)for(;j<=end;j++,k++)arr[k]=copy[j];elsefor(;i<=m;i++,k++)arr[k]=copy[i];_}voidmergeSort(intarr[],intleft,intright){//T(n)=2T(n/2)+O(n)if(left==right)//basiccasereturn;else{//recursivecaseintmid=(left+right)/2;//dividemergeSort(arr,left,mid);//T(n/2)mergeSort(arr,mid+1,right);//T(n/2)merge(arr,left,mid,right);//combine:O(n)}}4.调试过程及运行结果(详细记录在调试过程中出现的问题及解决方法。记录实验执行的结果)右边是归并排序左边是快速排序

TOC\o"1-5"\h\z请输入数组古小n:8■请输入数组大小n:8请输入数组元素:■请输入数据：右边是归并排序941-4011-30L90■941—01]-30190快速排序后的数组：■归并排序后的数组，-30-4014911L90■-30-4014911190Processreturned0(0x0)executiontime:£511s■processreturned0(0x0)executiontime:1,564s*S.B==_!a.测试数据二:测试数据三:测试数据四:商输入数据快速拌序后的数组归并排序后的数组ProcessreturnedexecutiontimeToc&ssreturned清输入数组大小请输入数组元谖executiontine测试数据五:测试数据二:测试数据三:测试数据四:商输入数据快速拌序后的数组归并排序后的数组ProcessreturnedexecutiontimeToc&ssreturned清输入数组大小请输入数组元谖executiontine测试数据五:5.总结（对实验结果进行分析，问题回答，实验心得体会及改进意见）在使用分而治之策略解决问题时候，要考虑：把原问题分解成规模较小的子问题后，在子问题容易求解的情况下，能否利用其结果使原问题得到解决。主要步骤有：Divide：将原问题分解Conquer:解决子问题Combine:利用子问题的解，解决原问题（不是必须，有时候子问题解决的同时原问题也解决了）6.附录（程序源代码等）#include<stdio.h>#include<stdlib.h>voidquickSort(intleft,intright,inta[]){if(left>=right)return;//basiccase:O(1)else{//recursivecaseinti=left;intj=right;//conquerinttemp=a[left];

//O(n)intflag=1;while(j!=i){while(flag&&j!=i){if(a[j]<=temp){flag=0;a[i]=a[j];}elsej--;}while(flag==0&&j!=i){if(a[i]>temp){flag=1;a[j]=a[i];}else//conquer//O(n)}}a[i]=temp;quickSort(left,i-1,a);quickSort(i+1,right,a);}}//divide(以i为左右边界)//T(n/2)//T(n/2)intmain(){intn;printf("请输入数组大小n:");scanf("%d",&n);inta[n];printf(-请输入数组元素：")；for(inti=0;i<n;i++){scanf("%d",&a[i]);}quickSort(0,n-1,a);for(inti=0;i<n;i++)printf("%d",a[i]);return0;}#include<stdio.h>#include<stdlib.h>voidmerge(intarr[],intleft,intmid,intright){//O(n)intm=mid-left;intend=right-left;intcopy[end+1];inti,j,k;for(i=0,j=left;i<=end;i++,j++)//O(n)copy[i]=arr[j];i=0;j=m+1;k=left;while(i<=m&&j<=end){//O(n)if(copy[i]<copy[j])(arr[k]=copy[i];i++;}else{arr[k]=copy[j];j++;}k++;}if(i>m)//O(n)for(;j<=end;j++,k++)arr[k]=copy[j];elsefor(;i<=m;i++,k++)arr[k]=copy[i];}voidmergeSort(intarr[],intleft,intright){//T(n)=2T(n/2)+O(n)if(left==right)return;else{intmid=(left+right)/2;//dividemergeSort(arr,left,mid);//T(n/2)mergeSort(arr,mid+1,right);//T(n/2)merge(arr,left,mid,right);//combineO(n)}}intmain(){inti=0;intn;printf("请输入数组大小n:");s