基于分治
快排是先分完再递归两边
归并是先递归，后合二为一

快速排序

在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

  1. 找一个参照点x
  2. 让x的左边都小于x，右边都大大于x

  3. 以 J 为中点，递归左边和右边

    1. void quick_sort(int q[], int l, int r)
    2. {
    3.  if (l >= r) return; //只有一个或为零时，结束 
    5.  int i = l - 1, j = r + 1, x = q[l + r >> 1]; // 这里的-1和+1会在下面的do循环中去掉 
    6.  while (i < j)
    7.  {
    8.      do i ++ ; while (q[i] < x); // 找到左边比x大(>=)的数 
    9.      do j -- ; while (q[j] > x);  // 找到右边比x小(<=)的数 
    10.      if (i < j) swap(q[i], q[j]);  //判断是否左边小于右边，然后交换 
    11.  }
    12.  quick_sort(q, l, j), quick_sort(q, j + 1, r); //递归左右两边 
    13. }

    归并排序

  4. [L,R] => [L,mid] , [mid+1,R] ;

  5. 递归排序[L,mid]和[mid+1,R];

  6. 归并，将左右两个有序序列合并成一个有序序列；

    1. void merge_sort(int q[], int l, int r)//归并排序
    2. {
    3.  if (l >= r) return;
    5.  int mid = l + r >> 1;
    6.  //先递归，递归到最后 
    7.  merge_sort(q, l, mid);
    8.  merge_sort(q, mid + 1, r);
    9.  //递归到最后，就是两个数 
    11.  int k = 0, i = l, j = mid + 1;
    12.  //左右遍历两个数组 
    13.  while (i <= mid && j <= r) //将这两个数进行比较 
    14.  //tem是一个临时数组 
    15.      if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];  
    16.      else tmp[k ++ ] = q[j ++ ];
    17.  //把剩下的几个的放进去 
    18.  while (i <= mid) tmp[k ++ ] = q[i ++ ];
    19.  while (j <= r) tmp[k ++ ] = q[j ++ ];
    20.  //再改变q数组 
    21.  for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    22. }