1 自顶向下的归并排序

  1. /**
  2.  * 归并排序的递归方法
  3.  */
  4. public class MergeSort implements Sort {
  6.     private int[] aux;
  8.     @Override
  9.     public void sort(int[] arr) {
  10.         aux = new int[arr.length];
  11.         mergeSort(arr, 0, arr.length - 1);
  12.     }
  14.     // 定义排序的区间是 [l, r] 闭区间
  15.     private void mergeSort(int[] arr, int l, int r) {
  16.         if (l >= r)
  17.             return;
  19.         int mid = l + (r - l) / 2;
  21.         mergeSort(arr, l, mid);
  22.         mergeSort(arr, mid + 1, r);
  24.         merge(arr, l, mid, r);
  25.     }
  27.     // 归并方法
  28.     private void merge(int[] arr, int l, int mid, int r) {
  30.         System.arraycopy(arr, l, aux, l, r - l + 1);
  32.         int i = l;
  33.         int j = mid + 1;
  35.         for (int k = l; k <= r; k++) {
  36.             if (i > mid)
  37.                 arr[k] = aux[j++];
  38.             else if (j > r)
  39.                 arr[k] = aux[i++];
  40.             else if (aux[i] <= aux[j])
  41.                 arr[k] = aux[i++];
  42.             else
  43.                 arr[k] = aux[j++];
  44.         }
  45.     }
  46. }

2 自底向上的归并排序

  • sz：每次要归并的数组的长度，从1开始，之后每次的长度变为原来的2倍，即sz += sz；另外sz可以等于数组的长度；
  • i：代表第一个归并数组的起始位置，从0开始，每次递增2个size长度，即i += sz + sz；
  • 每次归并的数组为 [i, i + sz - 1] 和 [i + sz, i +2sz - 1];
  • 边界问题：
  1. 确保第二个数组的起始位置不越界，即i + sz < arr.length；

  2. 确保第二个数组的结束位置不越界，即每次的取值为：组长度与i + sz + sz - 1的较小的值。

    1. public class MergeSortBU implements Sort {
    3.  @Override
    4.  public void sort(int[] arr) {
    5.      for (int sz = 1; sz <= arr.length; sz += sz) {
    6.          for (int i = 0; i + sz < arr.length; i += sz + sz) {
    7.              merge(arr, i, i + sz - 1, Math.min(arr.length - 1, i + sz + sz - 1));
    8.          }
    9.      }
    10.  }
    11. }

    3 扩展

  • 自底向上的归并排序并没有使用数组的索引，所以可以将此方法用到链表上；

  • 完成对链表的自底向上的归并排序。

  • [ ] 148. 排序链表

    在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。