快排

  1. 确定分界点 q[l]
  2. 调整区间（左边区间的值小于分界点对应的值，右边区间的值大于分界点对应的值）

  3. 递归处理左右两段

    1. //快排模板
    2. private static void quickSort(Integer[] arr, int l, int r) {
    4.    if (l >= r) return;
    6.    //分界点
    7.    int x = arr[l];
    9.    //定义两个指针
    10.    int i = l - 1;
    11.    int j = r + 1;
    13.    while (i < j) {
    14.        //分区
    15.        do i ++; while (arr[i] < x);
    16.        do j --; while (arr[j] > x);
    17.        if (i < j) swap(arr, i, j);
    18.    }
    20.    //递归处理左右两边
    21.    quickSort(arr, l, j);
    22.    quickSort(arr, j + 1, r);
    23. }

    归并排序

  4. 确定分界点：mid= (l + r) / 2

  5. 递归排序

  6. 归并-合二为一

    1. //归并排序模板
    2. private static void mergeSort(Integer[] q, int l, int r) {
    4.      if (l >= r) return;
    6.      //确定分界点
    7.      int mid = l + r >> 1;
    8.      int i = l;
    9.      int j = mid + 1;
    10.      int k = 0;
    12.      //递归排序
    13.      mergeSort(q, l, mid);
    14.      mergeSort(q, mid + 1, r);
    16.      //归并-合二为一
    17.      while (i <= mid && j <= r)
    18.          if (q[i] < q[j]) temp[k ++] = q[i ++];
    19.          else temp[k ++] = q[j ++];
    20.      while (i <= mid) temp[k ++] = q[i ++];
    21.      while (j <= r) temp[k ++] = q[j ++];
    23.      //赋值
    24.      for (i = l, j = 0; i <= r; i ++, j ++) q[i] = temp[j];
    25.  }