# 前言

排序算法的成本模型计算的是比较和交换的次数。less()方法对元素进行比较，exch()方法将元素交换位置。

  1. public static void exch(Comparable[] a, int i, int j) {
  2.     Comparable temp = a[i];
  3.     a[i] = a[j];
  4.     a[j] = temp;
  5. }
  7. public static boolean less(Comparable a, Comparable b) {
  8.     return a.compareTo(b) < 0;
  9. }

# 原地归并的抽象方法

该方法将所有元素复制到了aux[]中，然后再归并回a[]中。方法在归并（第二个 for 循环）进行了 4 个条件判断：

  • 左半边用尽，取右半边的元素；
  • 右半边用尽，取左半边的元素；
  • 右半边的当前元素小于左半边的当前元素，取右半边的元素；

  • 右半边的当前元素大于等于左半边的元素，取左半边的元素；

    * 实现

    1. public static void merge(Comparable[] a, int start, int mid, int end) {
    2.   int i = start, j = mid + 1;
    4.   for (int k = start; k <= end; k++) {
    5.       aux[k] = a[k];
    6.   }
    8.   for (int k = start; k<= end; k++) {
    9.       if (i > mid) a[k] = aux[j++];
    10.       else if (j > end) a[k] = aux[i++];
    11.       else if (less(a[j], a[i])) a[k] = aux[j++];
    12.       else a[k] = a[i++];
    13.   }
    14. }

    # 自顶向下的归并排序

    自顶向下的归并排序应用了分治的思想，要对数组 a 排序，现将数组分为a[start, mid]和a[mid + 1, end]两个部分，分别通过递归的调用来将它们单独排序，最后将有序的子数组归并为最终的结果。
    20161009190940095.gif

    * 实现

    ```java private static Comparable[] aux; // 归并所需的辅助数组

public static void sort(Comparable[] a) { aux = new Comparable[a.length]; // 一次性分配空间 sort(a, 0, a.length - 1); }

private static void sort(Comparable[] a, int start, int end) { if (end <= start) return;

  1. int mid = (start + end) / 2;
  2. sort(a, start, mid);        // 将左半边排序
  3. sort(a, mid + 1, end);        // 将右半边排序
  4. merge(a, start, mid, end);    // 归并结果

}

  1. <a name="Rk8vt"></a>
  2. # # 自底向上的归并排序
  3. 实现归并排序的另一种方法是先归并那些微型数组，然后在成对归并得到的子数组，如此这般多次的遍历整个数组，直到我们将整个数组合并到一起。
  5. 自底向上的归并排序比较适合链表组织的数据。
  6. > 可以将链表按照大小为 1 的子链表进行排序，然后是大小为 2 的链表，然后是大小为 4 的子链表等。
  8. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/2323967/1645791127609-a1baa652-eb37-450b-aa64-ab95cd48a205.png#clientId=udb19aa39-3378-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=326&id=ua836e0f8&margin=%5Bobject%20Object%5D&name=image.png&originHeight=354&originWidth=574&originalType=binary&ratio=1&rotation=0&showTitle=true&size=65063&status=done&style=none&taskId=u074e5ef5-7cc4-4b18-8e37-c56084675cb&title=%E5%9B%BE%E4%B8%AD%E4%B8%BA%E8%87%AA%E5%BA%95%E5%90%91%E4%B8%8A%E7%9A%84%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E4%B8%AD%E5%BD%92%E5%B9%B6%E7%9A%84%E8%BD%A8%E8%BF%B9&width=528 "图中为自底向上的归并排序中归并的轨迹")
  9. <a name="uNxhR"></a>
  10. ## * 实现
  11. ```java
  12. public class MergeBU {
  13.     private static Comparable[] aux;
  15.     public static void sort(Comparable[] a) {
  16.         int N = a.length;
  17.         aux = new Comparable[N];
  19.         for (int size = 1; size < N; size = 2 * size) {
  20.             for (int start = 0; start < N - size; star += 2 * size) {
  21.                 merge(a, start, start + size - 1, Math.max(start + 2 * size - 1, N - 1);
  22.             }
  23.         }
  24.     }
  25. }

# 特点

  • 归并排序的空间复杂度不是最优的，辅助数组 aux 使用的空间和数组的大小成正比。
  • 和选择排序一样，归并排序的性能不受输入数据的影响，但是表现比选择排序好。

  • 自底向上和自顶向上的归并排序所用的比较次数和数组访问次数相同，只是顺序不同。

    # 复杂度分析

  • 时间复杂度

    • 最好：归并排序 - 图2
    • 最坏：归并排序 - 图3
    • 平均：归并排序 - 图4
  • 空间复杂度 归并排序 - 图5
  • 稳定