分治法
快速排序法
-
分解a[s…t]分解成a[s…i-1]和a[i+1…t],其中i 为划分的基准
-
求解子问题：若子序列的长度为0或为1，则他是有序的，直接返回；否则递归地求解各个子问题。
-
合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作。
-
例：
int Partition(int a[],int s,int t){//划分算法 int i=s,j=t; int tmp=a[s]; //用序列的第一个记录作为基准 while(i!=j){ //从序列两端交替向中间扫描，直至i=j为止 while(j>i&&a[j]>=tmp) j--; //从右向左扫描关键字小于tmp的a[j] a[i]=a[j]; //将a[j]迁移到a[i]位置 while(i<j&&a[i]<=tmp) i++; //从左向右，找到第一个关键字大于tmp的a[i] a[j]=a[i]; //将a[i]后移到a[j]的位置 } a[i]=tmp; return i; } /*{2,5,1,7,10,6,9,4,3,8} 以2为基数 两个指针:左子针left，右子针right 从右向左搜索小于基数的数，从左向右搜素大于基准的数 a[i]=a[j]; //将a[j]迁移到a[i]位置 a[j]=a[i]; //将a[i]后移到a[j]的位置 1<2 i=0,j=2 1,5,1,7,10,6,9,4,3,8 然后从left,5>2,j=3,i=1 1,5,5,7,10,6,9,4,3,8 循环搜索 i=1,j=3 后方无小于基数2的数将i=1置为2 1,2,5,7,10,6,9,4,3,8 执行QuikSort(a,s,i-1) i的左边不变 i的右边以5为基准 执行 QuickSort(a,i+1,t);// */ void QuikSort(int a[],int s,int t){ if(s<t){ int i=Partition(a,s,t); QuikSort(a,s,i-1);//对左子序列递归排序 QuickSort(a,i+1,t);//对右子序列递归排序 } } -
求前k个
void QuickSort(T a[],int s,int t,int k){ int i; if(s<t){ i=Partition(a,s,t); if(k<i+1) QuickSort(a,s,i-1,k); else if(k>i+1) QuickSort(A,i+1,k) } } T solve(T a[],int n,int k){ QuickSort(a,0,n-1,k); for(int i=0;i<k;i++) printf("%d",a[i]); printf("\n"); }
归并排序法
-
将a[0…n-1]看成n个长度为1的有序表，将相邻的k（k>=2）个有序表成对归并，得到k/n个长度为k的有序子表；然后再将浙西有序子序列继续归并，得到n/k的平方的有序子表，如此反复进行下去，最后得到一个长度为n的有序表，k为2时为二路归并排序
-
例：
2,5,1,7,10,6,9,4,3,8 2,5 1,7 10,6 9,4 3,8 1,2,5,7 4,6,9,10 3,8 1,2,4,5,6,7,9,10 3,8 1,2,3,4,5,6,7,8,9,10 -
分治策略如下:
- 循环log2 n,length依次取1、2、4、。。。。每次执行如下
- 分解：将原序列分解成length长度的若干子序列
- 合并：将相邻的两个子序列调用Merge算法排序产生一个有序子序列
-
算法设计:
- 自底向上
void Merge(int a[],int low ,int mid ,int high) { int *tmpa; int i=low,j=mid+1,k=0; tmpa=(int *)malloc((hight-low+1)*sizeof(int)); while(i<=mid&&j<=high) { if(a[i]<=a[j])//将第一个子表中的元素放入tmpa { tmpa[k]=a[i]; i++; k++; } else { tmpa[k]=a[j];//将第二个子表中的元素放入tmpa j++; k++; } } while(i<=mid)//将第一子表余下部分复制到tmpa {tmpa[k]=a[i];i++;k++} while(j<=high)//将第二个子表余下的部分复制到tmpa {tmpa[k]=a[j];j++;k++} for(k=0;i=low;i<=high;k++,i++)//将tmpa复制回a中 a[i]=tmpa[k]; free(tmpa);//释放tmpa所占内存空间 } void MergePass(int a[],int length,int n) { int i; for(int i=0;i+2*length-1<n;i=i+2*length)//归并length长的两相邻子表 Merge(a,i,i+length-1,i+2*length-1); if(i+length-1<n) //余下两个子表，后者长度小于length Merge(a,i,i+length-1,n-1);//归并这两个子表 } void MergeSort(int a[],int n) { int length; for(length=1;length<n;length=2*lenth) MergePass(a,length,n); }- 自顶向下
/*2,5,1,7,10,6,9,4,3,8 2,5,1,7,10 6,9,4,3,8 2,5,1 7,10 6,9,4 3,8 2,5 1 7,10 6,9 4 3 8 2 5 7 10 6 9 2,5 6,9 1,2,5 4,6,9 1,2,5,7,10 3,4,6,8,9 1,2,3,4,5,6,7,8,9 */ void MergeSort(int a[],int low,int high) { int mid; if(low<high)//子序列有两个或以上元素 { mid=(low+high)/2;//取中间位置 MergeSort(a,low,mid);//对a[low..mid]子序列排序 MergeSort(a,mid+1,high);//对a[mid+1...high]子序列排序 Merge(a,low,mid,high);//对两子序列合并，见前面的算法 } } -
求最大和次大
-
分解：按中间位置mid=(low+high)/2划分为a[low…mid]和a[mid+1…high]左右两个区间(注意左区间包含a[mid])
-
求分解子问题：求出左区间最大值lmax1和次大值lmax2，求出右区间最大值rmax1和次大值rmax2
-
合并：若lmax1>rmax1,则max1=lmax1,max2=MAX{lmax2,rmax1}m否则max1=rmax1,max2={
lmax1,rmax2}
#include<algorithm> #include<iostream> #include<stdio.h> using namespace std; #define INF 600000; //在vs6中max要_cpp_max void solve(int a[],int low,int high,int &max1,int &max2) { if(low==high) //区间中只有一个元素 { max1=a[low]; max2=-INF; } else if(low==high-1) //区间只有两个元素 { max1=_cpp_max(a[low],a[high]); max2=_cpp_min(a[low],a[high]); } else { int mid=(low+high)/2;//区间有两个以上元素 int lmax1,lmax2; solve(a,low,mid,lmax1,lmax2);//左区间求lmax1和lmax2 int rmax1,rmax2; solve(a,mid+1,high,rmax1,rmax2);//右区间求rmax1和rmax2 if(lmax1>rmax1) { max1=lmax1; max2=_cpp_max(lmax2,rmax1);//lmax2,rmax1中求次大元素 } else { max1=rmax1; max2=_cpp_max(lmax1,rmax2); //lmax1、rmax中求次大元素 } } } -
-
折半查找