归并排序

#personal/blog #algorithm/sorting

概述

归并排序利用了分治的思想，将一整个待排序的数组分解成若干的小数组，然后再通过“融合”操作小数组间变得有序，接下来再使整个数组有序的排序方法。自然而然的，就要利用到递归的思想。
相对于选择排序和冒泡排序，其时间复杂度更低, 因此其效率也更高。但由于递归压栈的存在，效率更高的代价是空间的浪费。
T(N)=T(N/2)+O(N)，即 O(N∗log2N)

思路分解

  1. 我们首先要“缩小”排序数组，即利用递归。先设定递归结束的条件——当数组只剩下一个元素时，数组默认是有序的，此时递归结束。且每一次按照数组的中点来切分；
  2. 当我们排序好了之后，需要把两串数组融合在一起使其整体有序，所以我们还需要一个辅助函数 merge 来完成这个功能；
  3. 此时，我们的逻辑部分就完成了，只需要在主函数处调用即可。

分步实现

  1. 首先要实现递归的逻辑：
private static void process(int[] arr, int L, int R) {  
    if (L == R) {       //递归结束条件  
        return;  
    }  
    int mid = L + ((R - L) >> 1);       //找中间位置  
    process(arr, L, mid);  
    process(arr, mid + 1, R);  
    merge(arr, L, mid, R);  //融合两个有序数组，使其整体有序
}
  1. 实现融合的具体逻辑（稍复杂一些）：
private static void merge(int[] arr, int L, int M, int R) {  
    int p1 = L;  
    int p2 = M + 1;  
    int i = 0;  
    int[] help = new int[R - L + 1];  
    while (p1 <= M && p2 <= R) {  
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];  //逻辑1
    }  
    while (p1 <= M) {  //逻辑2
        help[i++] = arr[p1++];  
    }  
    while (p2 <= R) {  
        help[i++] = arr[p2++];  
    }  
    for (int j = 0; j < help.length; j++) {  //逻辑3
        arr[L + j] = help[j];  
    }  
}

解读： （默认以 p2 代表 p2 指向的元素）

  1. 以 M 为分界，左右两边均是已经排序好的“数组”；
  2. 第一个数组的第一个元素（下标为 L）由 p1 指向，第二个数组的第一个元素（下标为 M+1）由 p2 指向；
  3. 执行“逻辑 1”，若 p1 指向的元素小于 p2 ，则将左边的元素放入 help 临时数组中，p1 后移一位；若 p1>p2，则将 p2 放入 help 中，p2 后移。直到其中一个指针越界为止；
  4. 接下来，要处理那些还没有被处理的元素，执行“逻辑 2”；
  5. 最后把临时的 help 数组存入 arr；

与选择排序的区别

通过观察上述代码片段不难发现为什么选择排序的效率低了：
因为选择排序遍历了一遍代码只找到了一个合适的位置，而归并排序完成一轮递归就已经排完了一半了。
不论是选择、冒泡还是插入排序都浪费了很多的比较行为——多次的比较行为只完成了相当有限的工作。