快排(分治)

将小于给定值num的数放在数 组的左边，大于num的数放在数组的右边，定值num不能在数组中存在

  1. while(i<j){
  2.         do i++;while(a[i]<num);
  3.         do j--;while(a[j]>num);
  4.         if(i<j) swap(a[i],a[j]);
  5. }
  1. 确定分界点 q[l+r>>1]
  2. 调整区间 小于分界点的在左边， 大于分界点的在右边
  3. 递归处理左右两段

    模板

    1. void quick_sort(int q[],int l,int r)
    2. {
    3.  if(l>=r) return;
    4.  int i = l-1,j = r+1, x = q[l+r>>1];
    5.  while(i<j){
    6.      do i++;while(q[i]<x);
    7.      do j--;while(q[j]>x);
    8.      if(i<j) swap(q[i],q[j]);
    9.  }
    10.  quick_sort(q,l,j),quick_sort(q,j+1,r);
    11. }

归并排序

  1. 确定分界点
  2. 递归排序left，right
  3. 归并 —- 合二为一

    模板

    1. void merge_sort(int q[],int l,int r)
    2. {
    3.  if(l>=r) return;
    4.  int mid = l+r>>1;
    5.  merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    6.  int i = l,j = mid+1,k = 0;
    7.  while(i<=mid and j<=r)
    8.  { if(q[i]<q[j]) tmp[k++] = q[i++];
    9.    else tmp[k++] = q[j++];
    10.  }
    11.  while(i<=mid) tmp[k++] = q[i++];
    12.  while(j<=r) tmp[k++] = q[j++];
    13.  for(i = l,j = 0;i<=r;i++,j++) q[i] = tmp[j];
    14. }