我们都知道STL中最常用的排序库函数：sort(v.begin(),biend())。 给出的是升序排序。 我一般不喜欢用迭代器，我一般用这个格式，对数组进行排序，指针替代迭代器。
sort(a,a+n)//升序排序sort(a,a+n,cpm);int cmp(type a,type b){//定义的比较格式}
这里我们来手动实现归并排序和快素排序，对于快排排序，我们知道它的运行效率和关键字的A[p]选择有关，我们这里没有考虑，即没有给出随机选择下标的算法，值给出了普通的关键代码，读者可以自己实现随机的快排函数，而归并排序也是只给出了递归的程序。
归并排序： *是一种递归的排序算法，对于输入数组A[1..n], *我们可以先排序前半段A[1..n/2],和后半段A[n/2+1..n]; *然后在合并到A[1..n]，此时A[1..n]以完成排序 *算法分析： *1、分解：将n个元素分成含有n/2个元素的子序列 *2、解决：用合并平排序法对两个子序列递归的排序 *3、合并两个已排序的子序列得到排序结果 *注：对于子序列，其长度为1时，，递归结束，单个元素被视为已排序
/** *对于排好序的子数组A[l..m]和A[m+1..r]，–>A[l..r](已排序) */[r-l+1];int i=l,j=m+1,k=1;while(i<=m&&j<=r){if(A[i]<=A[j]) B[k++]=A[i++];else B[k++]=A[j++];}//处理尾部while(i<=m){B[k++]=A[i++];}while(j<=r){B[k++]=A[j++];}//copy(A,B)for(i=l;i<=r;i++){A[i]=B[i-l+1];}delete B;}/** *归并排序，调用MergeSort(A,1,n); */void MergeSort(int *A,int l,int r){if(l<r){int m=(l+r)/2;MergeSort(A,l,m);//递归左排MergeSort(A,m+1,r);//递归右排Merge(A,l,m,r);//合并两端字数组}}
快速排序QuickSort(A,1,n); *算法如下： *1、分解将数组A[p..r]划分为两个字数组A[p..q-1]和A[q+1..r],使得 *A[p..q-1]中的每个元素都小于等于A[q],并且，小于等于A[q+1..r]， * 下标q也在这个划分过程中确定，已q为分界线划分 *2、解决递归快速排序，对字数组A[p,q-1]和A[q+1..r],此时A[q]已在排序后的位置 *3、因为两个字数组是就地排序的，不需合并就已经排好序
代码：
/** *划分函数 */int Quick_Init(int *A,int p,int r){//已a[p]作为划分关键字int i=p+1,j=r;while(true){while(A[i]<=A[p]) ++i;while(A[j]>A[p]) –j;if(j<=i) break;else{swap(A[i],A[j]);//交换护不满足的两个元素++i; –j;//进行下次判断}}swap(A[p],A[j]);//将关键字与最后一个j的位置交换，此时A[p]已完成排序return j;//返回关键字的位置}void QuickSort(int *A,int p,int r){if(p<r){//>=2，就进行划分并排序int q=Quick_Init(A,p,r);QuickSort(A,p,q-1);//左排QuickSort(A,q+1,r);//右排}}测试主程序：int main(){int A[9]={0,4,8,2,3,5,2,1,6};PT(A,8);MergeSort(A,1,8);QuickSort(A,1,8);PT(A,8);return 0;}注：PT(A,n)的定义为#define PT(A,n) for(int i=1;i<=n;i++) cout<<A[i]<<” “; cout<<endl;
先知三日，富贵十年。
