分而治之合并排序

关注「码哥字节」设置星标,吸收最新手艺干货提升自我。本文完整源码详见 Github:https://github.com/UniqueDong/algorithms.git

前面我们学习了时间庞大度 O(n²) 的经典排序算法:冒泡排序、插入排序、选择排序,今天我们来学习时间庞大度为 O(nlogn) 的合并排序,这种排序头脑也加倍常用。

合并排序和快速排序都用到了 分治头脑

作为一种典型的分而治之头脑的算法应用,合并排序的实现由两种方式:

  • 自上而下的递归(所有递归的方式都可以用迭代重写,以是就有了第 2 种方式);
  • 自下而上的迭代;

原理

把数组从中心分成左右两部门,然后对左右两部门划分排序,再将排序号的两部门合并在一起,最后整个序列有序。实在就是运用了分治头脑,顾名思义,就是分而治之,将一个大问题剖析成小的子问题。

是不是跟递归很像,分治一样平常都是用递归来实现。分治是一种解决问题的处置头脑,递归是一种编程技巧。

递推公式

之前我们在 递归 篇说过,递归代码的技巧就是剖析递推公式,找出终止条件,然后把递推公式翻译代码。

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件:
p >= r 不用再继续剖析

我来解释一下这个递推公式。

merge_sort(p…r) 示意,给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题,merge_sort(p…q) 和 merge_sort(q+1…r),其中下标 q 即是 p 和 r 的中心位置,也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从 p 到 r 之间的数据就也排好序了。

public static void mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

public static void sort(int[] arr, int left, int right) {
    // 递归终止条件
    if(left >= right) {
        return;
    }
    // 获取 left right 之间的中心位置
    int mid = left + ((right - left) >> 1);
    // 分治递归
    sort(arr, left, mid);
    sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// 合并数据
public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = 0;
    int p1 = left;
    int p2 = mid + 1;
    // 对照左右两部门的元素,哪个小,把谁人元素填入temp中
    while(p1 <= mid && p2 <= right) {
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 上面的循环退出后,把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while(p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while(p2 <= right) {
        temp[i++] = arr[p2++];
    }
    // 把最终的排序的效果复制给原数组
    for(i = 0; i < temp.length; i++) {
        arr[left + i] = temp[i];
    }
}

性能剖析

第一,合并排序是稳定的排序算法吗?

你应该能发现,合并排序稳不稳定要害要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部门代码。

在合并的历程中,若是 A[left…mid] 和 A[mid+1…right] 之间有值相同的元素,那我们可以像伪代码中那样,先把 A[left…mid] 中的元素放入 tmp 数组。这样就保证了值相同的元素,在合并前后的先后顺序稳定。以是,合并排序是一个稳定的排序算法。

第二,合并排序的时间庞大度是多少?

合并排序涉及递归,时间庞大度的剖析稍微有点庞大。我们正好借此机会来学习一下,若何剖析递归代码的时间庞大度。

在递归那一节我们讲过,递归的适用场景是,一个问题 a 可以剖析为多个子问题 b、c,那求解问题 a 就可以剖析为求解问题 b、c。问题 b、c 解决之后,我们再把 b、c 的效果合并成 a 的效果。

若是我们界说求解问题 a 的时间是 T(a),求解问题 b、c 的时间划分是 T(b) 和 T( c),那我们就可以获得这样的递推关系式:其中 K 即是将两个子问题 b、c 的效果合并成问题 a 的效果所消耗的时间。

T(a) = T(b) + T(c) + K

我们可以获得一个主要的结论:不仅递归求解的问题可以写成递推公式,递归代码的时间庞大度也可以写成递推公式。

我们假设对 n 个元素举行合并排序需要的时间是 T(n),那剖析成两个子数组排序的时间都是 T(n/2)。我们知道,merge() 函数合并两个有序子数组的时间庞大度是 O(n)。以是,套用前面的公式,合并排序的时间庞大度的盘算公式就是:

T(1) = C;   n=1 时,只需要常量级的执行时间,以是示意为 C。
T(n) = 2*T(n/2) + n; n>1

通过这个公式,若何来求解 T(n) 呢?还不够直观?那我们再进一步剖析一下盘算历程。

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步剖析推导,我们可以获得 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们获得 k=log2n 。我们将 k 值代入上面的公式,获得 T(n)=Cn+nlog2n 。若是我们用大 O 标记法来示意的话,T(n) 就即是 O(nlogn)。以是合并排序的时间庞大度是 O(nlogn), 不管是最好情形、最坏情形,照样平均情形,时间庞大度都是 O(nlogn)。

第三,合并排序的空间庞大度是多少?

合并排序的时间庞大度任何情形下都是 O(nlogn),看起来异常优异。(待会儿你会发现,即便是快速排序,最坏情形下,时间庞大度也是 O(n²)。)然则,合并排序并没有像快排那样,应用普遍,这是为什么呢?由于它有一个致命的“弱点”,那就是合并排序不是原地排序算法。

这是由于合并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助分外的存储空间。

实际上,递归代码的空间庞大度并不能像时间庞大度那样累加。刚刚我们忘记了最主要的一点,那就是,只管每次合并操作都需要申请分外的内存空间,但在合并完成之后,暂且开拓的内存空间就被释放掉了。在随便时刻,CPU 只会有一个函数在执行,也就只会有一个暂且的内存空间在使用。暂且内存空间最大也不会跨越 n 个数据的巨细,以是空间庞大度是 O(n)。

课后思索

现在你有 10 个接口接见日志文件,每个日志文件巨细约 300MB,每个文件里的日志都是根据时间戳从小到大排序的。你希望将这 10 个较小的日志文件,合并为 1 个日志文件,合并之后的日志仍然根据时间戳从小到大排列。若是处置上述排序义务的机械内存只有 1GB,你有什么好的解决思绪,能“快速”地将这 10 个日志文件合并吗?

回台回复:日志排序,即可获取谜底哦。

后台回复「加群」加入手艺群获取更多发展,最新内容一手掌握