合并、快速排序算法

快速排序算法1.#includestdio.h2.inta[101],n;//定义全局变量，这两个变量需要在子函数中使用3.voidquicksort(intleft,intright)4.{5.inti,j,t,temp;6.if(leftright)7.return;8.9.temp=a[left];//temp中存的就是基准数10.i=left;11.j=right;12.while(i!=j)13.{14.//顺序很重要，要先从右边开始找15.while(a[j]=temp&&ij)16.j--;17.//再找右边的18.while(a[i]=temp&&ij)19.i++;20.//交换两个数在数组中的位置21.if(ij)22.{23.t=a[i];24.a[i]=a[j];25.a[j]=t;26.}27.}28.//最终将基准数归位29.a[left]=a[i];30.a[i]=temp;31.32.quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程33.quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程34.}35.intmain()36.{37.inti,j,t;38.//读入数据39.scanf(%d,&n);40.for(i=1;i=n;i++)41.scanf(%d,&a[i]);42.quicksort(1,n);//快速排序调用43.44.//输出排序后的结果45.for(i=1;i=n;i++)46.printf(%d,a[i]);47.getchar();getchar();48.return0;49.}合并排序（递归）#includeiomanip.h//调用setw#includeiostream.h//将b[0]至b[right-left+1]拷贝到a[left]至a[right]templateclassTvoidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;isize;i++){a[left++]=b[i];}}//合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组btemplateclassTvoidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一个数组开头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(intj=0;jright-left+1;j++)//执行right-left+1次循环{if(a1couta1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到bif(a2couta2end){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果两个数组都没结束，比较元素大小，把较小的放入belse{b[bcout++]=a[a2cout++];continue;}}}//对数组a[left:right]进行合并排序templateclassTvoidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1];if(leftright){inti=(left+right)/2;//取中点MergeSort(a,left,i);//左半边进行合并排序MergeSort(a,i+1,right);//右半边进行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//从b拷贝回来}}intmain(){intn;cout请输入您将要排序的数目:;cinn;int*a=newint[n];cout请输入相应的数字：;for(inti=0;in;i++){cina[i];}MergeSort(a,0,n-1);cout排序结果:;for(intj=0;jn;j++){coutsetw(5)a[j];}coutendl;return1;}合并排序（非递归）#includestdio.hvoidprintArray(int*head,intlen){printf(\ndatas:);inti=1;for(i=1;i=len-1;i++){printf(%d,head[i]);}printf(\n);}voidcopyArray(int*head,int*tmp,intlen){inti=0;for(i=0;i=len;i++){head[i]=tmp[i];}}/****/voidMergeTwo(int*head,int*tmp,intl,intm,inth){printf(\nl:%dm=%dh=%d\n,l,m,h);inti=l,j=m+1,k=l;for(;i=m&&j=h;k++){if(head[i]=head[j]){tmp[k]=head[i++];}else{tmp[k]=head[j++];}}while(i=m){tmp[k++]=head[i++];}while(j=h){tmp[k++]=head[j++];}}/****/voidMergeSortFlag(int*head,int*tmp,intlen,intflag){inti=1;intt;while(i=(len-2*flag+1)){MergeTwo(head,tmp,i,i+flag-1,i+2*flag-1);i=i+2*flag;}printf(\ni=%d\n,i);if(i+flag-1len){MergeTwo(head,tmp,i,i+flag-1,len);}else{for(t=i;t=len;t++){tmp[t]=head[t];}}printf(flag:%d,flag);printArray(tmp,len+1);copyArray(head,tmp,len);}/****/voidMergeSort(int*head,int*tmp,intlen){intflag=1;while(flaglen){MergeSortFlag(head,tmp,len,flag);flag=2*flag;}}intmain(intargc,char*argv[]){intsrc[10]={-1,1,3,2,8,7,5,6,9,4};inttmp[10]={-1,0,0,0,0,0,0,0,0,0};printArray(src,10);MergeSort(src,tmp,9);printArray(tmp,10);getchar();return0;