排序算法 #5 归并排序

合并两个有序数组

现在有两个有序数组，分别是数组F={2, 4}和数组S={1, 3, 5}。

那么如何将这两个有序数组合并为一个有序数组呢？首先，需要开辟一个新的数组空间，其长度为数组F和数组S的长度之和，新开辟的空间用于保存合并结果。
接着，讲一下合并的思路，拿数组中的第一个数举例：

如果数组F中的第一个数小于等于数组S中的第一个数，那么就将数组F中的第一个数放入新开辟的数组中；
否则，将数组S中的第一个数放入新开辟的数组中，即数组F中的第一个数大于数组S中的第一个数时。

在这里，数组F中的第一个数是2，大于数组S中的第一个数1。因此将数组S中的第一个数，放入新开辟的数组空间中。
在将数组S中的第一个数1，放入新开辟的数组空间中后，接着需要比较的就是数组F中的第一个数2和数组S中的第二个数3。此时，3大于2，因此，数组F中的第一个数2放入新开辟的数组空间中。
接下来需要考察的是，数组F中的第二个数4和数组S中的第二个数3，由于4大于3，因此将数组S中的第二个数3放入新开辟的数组空间中。
接下来需要考察的是，数组F中的第二个数4和数组S中的第三个数5，由于4小于5，因此将数组F中的第二个数4放入新开辟的数组空间中。
在将数组F中的元素4放入新开辟的数组空间中后，数组F中元素全部考察完毕。接着要做的就是将数组S中剩余的元素5放入新开辟的数组空间中。
至此，就完成了两个有序数组F和S的合并。
上述合并两个有序数组为一个有序数组的过程，我们称之为归并。
02分治思想
分治思想说的是，对于一个复杂的问题，我们可以将其分解成多个类似的子问题。如果子问题不能求解，则继续将子问题分解为更小的子问题，直至子问题可以容易求解。接下来以数组{4, 2, 3, 1, 5}为例进行说明。
首先，可以将其拆分为两个子数组{4, 2}和{3, 1, 5}。
对于子数组{4, 2}，可进一步拆分为数组{4}和数组{2}；而数组{3, 1, 5}可以拆分为数组{3}和数组{1, 5}。
对于拆分出来的数组{1, 5}，可进一步拆分为数组{1}和数组{5}。
至此，数组{4, 2, 3, 1, 5}就被拆分成了数组{4}、{2}、{3}、{1}、{5}这五个子数组。

03分治和归并实现数组的排序
上面我们分别讲解了归并和分治这两个思想，接下来看如何通过这两个思想对数组进行排序。对于数组{4, 2, 3, 1, 5}通过分治之后，就变成了{4}、{2}、{3}、{1}、{5}这五个子数组。接下来要做的就是，对这五个子数组进行归并，使其从小到大排序。首先，对数组{1}和数组{5}进行归并。
数组{1}和数组{5}归并之后，子数组有4个，分别是数组{4}、{2}、{3}、{1, 5}。接着，对子数组{4}和子数组{2}进行归并，同时，对子数组{3}和子数组{1, 5}进行归并。
归并之后，子数组有两个，分别是数组{2, 4}和数组{1, 3, 5}，将其进行归并。
将这两个子数组进行归并之后，就完成了数组从小到大的排序。

04代码实现

public static int[] sort(int[] arr) {    if (arr.length == 1) {        return arr;    }
    // 拆分为子数组a和子数组b    int length = arr.length;    int mid = length/2;    int[] a = Arrays.copyOfRange(arr, 0, mid);    int[] b = Arrays.copyOfRange(arr, mid, length);
    // 分别对子数组a和子数组b进行排序    a = sort(a);    b = sort(b);
    // 归并排序后的子数组a和b    int[] res = merger(a, b);    return res;}
private static int[] merger(int[] a, int[] b) {    int[] res = new int[a.length + b.length];
    int aCur = 0;    int bCur = 0;    int resCur = 0;
    // 取子数组a和子数组b中的元素，进行比较    // 将较小的放入数组res中    while (aCur < a.length && bCur < b.length) {        if (a[aCur] <= b[bCur]) {            res[resCur] = a[aCur];            aCur++;        } else {            res[resCur] = b[bCur];            bCur++;        }
        resCur++;    }
    // 如果子数组a中还有元素，则依次放入res中    if (aCur < a.length) {        for (int i = aCur; i < a.length; i++) {            res[resCur] = a[i];            resCur++;        }    }
    // 如果子数组b中还有元素，则依次放入res中    if (bCur < b.length) {        for (int j = bCur; j < b.length; j++) {            res[resCur] = b[j];            resCur++;        }    }
    return res;}

更多相关文章

随机推荐