【算法】归并排序算法的讲解和代码实践

思路

有数组[2, 1, -3, -15, 25, 16, 0, 8]如下：

image.png

现对该数组进行排序，使用归并排序算法。
先来讲解一下归并排序的思路，大概分为如下几个步骤：

1. 先将原数组先进行拆分，拆分成若干个足够小的子数组；
2. 将子数组进行排序；
3. 将子数组一一进行归并，直到所有子数组被归并。

讲解

OK，思路了解了，下面就用图示来演示一下各个步骤是怎么做的。

1. 先将原数组先进行拆分，拆分成若干个足够小的子数组：

我们先把上面的数组进行第一次拆分：

image.png

拆分成了两部分，分别为[2, 1, -3, -15]和[25, 16, 0, 8]
这样的拆分不够小，我们继续进行拆分：

image.png

这样就又把两个子数组分别拆分成了更小的两个子数组[2, 1]、[-3, -15]、[25, 16]、[0, 8]。
好了，这样的拆分足够小了，进行下一步。

2. 将子数组进行排序：

排序后的四个子数组为：

image.png

子数组排序后，就该进行最后一步了。

3. 将子数组一一进行归并，直到所有子数组被归并：

先将第一个子数组和第二个子数组进行归并，归并的步骤其实也很简单，就是将两个子数组的元素从左到右依次进行比较，按顺序进行存放即可。
这时候需要创建一个空数组，对结果集进行一个存放。首先对比1和-15，1比-15要大，所以先把-15放到结果数组中：

image.png

然后对比1和-3,1依然是大于-3，所以把-3放到结果数组中：

image.png

这时候第二个子数组已经被搬空了，那么直接把第一个子数组的数据依次放入结果数组即可：

image.png

这样前面两个子数组就完成了归并操作。那么后面两个子数组也是同样的归并方式，归并结果如下：

image.png

这样就归并成了两个子数组，然后再对这两个子数组进行进一步的归并操作，操作依然跟上面是一样的，一个一个对比，最终就归并成了如下结果：

image.png

这样就完成了一个简单的归并排序。
但一般生产中可能需要排序的数据会比较大，那么拆分的时候可能拆分到15个左右元素的时候，就不再进行拆分了，而是使用插入排序的方式对子数组进行排序，然后再对排好序的子数组进行归并。

实现

下面来用代码实现一下归并排序：

    @Test
    public void sortTest() {
        int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8};
        int[] sortedArray = mergeSort(nums);
        System.out.println(Arrays.toString(sortedArray));
    }

    private int[] mergeSort(int[] nums) {
        // 数组大小小于2，直接返回
        if (nums.length < 2) {
            return nums;
        }
        // 数组大小等于2，排序并返回
        if (nums.length == 2) {
            if (nums[0] > nums[1]) {
                swap(nums, 0, 1);
            }
            return nums;
        }
        // 数组拆分
        int[] left = Arrays.copyOfRange(nums, 0, nums.length / 2);
        int[] right = Arrays.copyOfRange(nums, nums.length / 2, nums.length);
        // 递归归并
        return merge(mergeSort(left), mergeSort(right));
    }

    private int[] merge(int[] left, int[] right) {
        // 声明结果数组
        int[] result = new int[left.length + right.length];
        // 开始遍历，每次放入结果数组一个元素
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            // 如果左子数组已经归并完，直接放入右子数组
            if (i >= left.length) {
                result[index] = right[j++];
                // 如果右子数组已经归并完，直接放入左子数组
            } else if (j >= right.length) {
                result[index] = left[i++];
                // 如果两个子数组都没有归并完，比较大小并放入结果数组
            } else if (left[i] < right[j]) {
                result[index] = left[i++];
            }else{
                result[index] = right[j++];
            }
        }
        return result;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

这样就实现了一个简单的归并排序，看下执行结果：

image.png

其实这叫二路归并，另外还有多路归并，其实知道原理了，也不难实现，比如三路归并：

    @Test
    public void sortTest() {
        int[] nums = new int[]{2, 1, -3, -15, 25, 16, 0, 8};
        int[] sortedArray = mergeSort(nums);
        System.out.println(Arrays.toString(sortedArray));
    }

    private int[] mergeSort(int[] nums) {
        // 数组大小小于2，直接返回
        if (nums.length < 2) {
            return nums;
        }
        // 数组大小等于2，排序并返回
        if (nums.length == 2) {
            if (nums[0] > nums[1]) {
                swap(nums, 0, 1);
            }
            return nums;
        }
        // 数组拆分
        int[] left = Arrays.copyOfRange(nums, 0, nums.length / 3);
        int[] mid = Arrays.copyOfRange(nums, nums.length / 3, nums.length / 3 * 2);
        int[] right = Arrays.copyOfRange(nums, nums.length / 3 * 2, nums.length);
        // 递归归并
        return merge(mergeSort(left), mergeSort(mid), mergeSort(right));
    }

    private int[] merge(int[] left, int[] mid, int[] right) {
        // 声明结果数组
        int[] result = new int[left.length + mid.length + right.length];
        // 开始遍历，每次放入结果数组一个元素
        for (int index = 0, i = 0, j = 0, k = 0; index < result.length; index++) {
            if (i >= left.length) {
                if (j >= mid.length) {
                    result[index] = right[k++];
                } else {
                    if (mid[j] < right[k]) {
                        result[index] = mid[j++];
                    } else {
                        result[index] = right[k++];
                    }
                }
            } else if (j >= mid.length) {
                if (k >= right.length) {
                    result[index] = left[i++];
                } else {
                    if (left[i] < right[k]) {
                        result[index] = left[i++];
                    } else {
                        result[index] = right[k++];
                    }
                }
            } else if (k >= right.length) {
                if (left[i] < mid[j]) {
                    result[index] = left[i++];
                } else {
                    result[index] = mid[j++];
                }
            } else {
                if (left[i] < mid[j]) {
                    if (left[i] < right[k]) {
                        result[index] = left[i++];
                    } else {
                        result[index] = right[k++];
                    }
                } else if (left[i] >= mid[j]) {
                    if (mid[j] < right[k]) {
                        result[index] = mid[j++];
                    } else {
                        result[index] = right[k++];
                    }
                }
            }
        }
        return result;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

道理是一样的，执行结果也是一样的：

image.png

好的，归并排序就说这么多。有不对不完善的地方欢迎指正。