归并排序

今天我们来学习一种很重要的排序算法——归并排序。

归并排序已经是一种在面试过程中,经常会被要求手撕出来的排序算法,不过现在大家都很厉害了,基本都能把他写出来,导致面试官可能也慢慢觉得平常了。

都怪大家太卷了。

所以,如果在面试中面试官又问到这一问题时,你如何让你的表现让面试官对你抛媚眼,让他对你的印象分大涨,耐心看完这篇文章,相信你能够做到。

归并排序介绍

归并排序是一种基于分治思想的递归排序算法。

我们先介绍一下什么是分治。

分治算法是一种将一个复杂问题分解成更小的子问题,并且递归地解决这些子问题,最后将各个子问题的解合并起来得到原问题解的算法思想。

在分治算法中,通常将原始问题分割成多个独立且相同结构的子问题,然后递归地求解这些子问题。最后将子问题的解合并起来得到原问题的解。

简而言之,分治的核心是将大问题分解成相同的子问题,最后进行子问题的合并。

先分再治。

归并排序算法分析

具体的我们来学习归并排序的原理,大家都能更好的理解上面的话了。

我们的问题是将一个大数组变得有序。可以先(递归地)将其分成两半分别排序(分),最后要解决的就是如何合并两个有序的子数组(治)

当我们不断的通过递归将数组进行拆分,当最后子数组的长度为 1 时,就结束拆分了。

合并两个有序数组

我们采用双指针的方法,不断比较两个指针所指的元素,并选择小的元素(升序)


下面我们直接写代码吧,然后代码在给出解析,这样反而好理解,当然,如果你不懂递归,那肯定就不好理解的话,可以看我的算法系统课,那里有关于递归的讲解。

归并排序代码实现

public class Solution {

    int[] help;

    public int[] Sort (int[] nums) {
        // 关注点一
        help = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort (int[] nums, int l, int r) {
        // 当数组只有一个元素时,递归结束
        if (l >= r) {
            return;
        }
        // 关注点二
        int mid = l + (r - l) / 2;
        // 让数组左半部分有序
        mergeSort(nums, l, mid);
        // 让数组右半部分有序
        mergeSort(nums, mid + 1, r);
        // 关注点三
        if (nums[mid] > nums[mid + 1]) {
            // 把左右两部分合并起来
            merge(nums, l, mid, r);
        }
    }

    // 合并两个有序数组 [l, mid], [mid + 1, r]
    public void merge (int[] nums, int l, int mid, int r) {
        System.arraycopy(nums, l, help, l, r - l + 1);
        int i = l;
        int j = mid + 1;
        int k = l;
        while (i <= mid && j <= r) {
            // 关注点四
            nums[k++] = help[i] <= help[j] ? help[i++] : help[j++];
        }
        while (i <= mid) {
            nums[k++] = help[i++];
        }
        while (j <= r) {
            nums[k++] = help[j++];
        }
    }
}

对于代码我们有几个地方需要注意下,编码完,也可以跟面试官介绍代码中的以下几点:

  • 一:只使用一个辅助数组,节省空间
  • 二:我们采用 l + (r - l) / 2 这种方式来取最值,防止计算的时候溢出,当然你也可以使用位运算的技巧,l + (r - l) >> 1
  • 三:这一步是 优化点,对于两个有序数组的合并,如果数组 A 的末尾大于数组 B 的开头,那就不需要合并了
  • 四:为了保证 稳定性help[i] <= help[j] 都先取 help[i]

到这里,相信他会认为你在思考问题时是比较全面的。

目前我们所讲的归并排序的经典实现是通过递归来实现,也称之为 自顶向下 的思想。

一般来说,递归我们都可以转化为迭代的方式来实现,也就是 自底向上 的思想。

如果你还能跟面试官说你还会自底向上的解决方法,相信他对你的印象分一定是大涨!

自底向上的归并排序

思路分析:

我们先将长度为 1 的子数组两两合并,得到长度为 2 的有序的子数组。

下一步,将长度为 2 的子数组两两合并,得到长度为 4 的有序的子数组。

以此类推,则到将整个数组变得有序。

看代码。

public class Solution {

    int[] help;

    public int[] Sort (int[] nums) {
        help = new int[nums.length];
        // size:每次迭代的子数组的大小
        for (int size = 1; size < nums.length; size *= 2) {
            for (int l = 0; l + size - 1 < nums.length; l += size * 2) {
                int mid = l + size - 1;
                int r = Math.min(l + size * 2 - 1, nums.length - 1);
                merge(nums, l, mid, r);
            }
        }
        return nums;
    }

    // 合并两个有序数组 [l, mid], [mid + 1, r]
    public void merge (int[] nums, int l, int mid, int r) {
        System.arraycopy(nums, l, help, l, r - l + 1);
        int i = l;
        int j = mid + 1;
        int k = l;
        while (i <= mid && j <= r) {
            nums[k++] = help[i] <= help[j] ? help[i++] : help[j++];
        }
        while (i <= mid) {
            nums[k++] = help[i++];
        }
        while (j <= r) {
            nums[k++] = help[j++];
        }
    }
}

时间复杂度

归并排序的时间复杂度是 {O(NlogN)},其中 N 为待排序序列的长度。

因为归并排序是将序列分成两个长度相等或相差 1 的子序列,然后递归排序这两个子序列,最后再合并这两个子序列,整个过程需要 logN 次递归,每次递归需要 {O(N)} 的时间复杂度,所以总的时间复杂度是 {O(NlogN)}

如果大家想了解严格的数学证明归并排序的时间复杂度,推荐看下算法 4 关于这一块的章节。

归并排序虽然擅长处理大规模数组,但是当我们递归到一定的深度,对于小规模数组,其实是可以使用插入排序来进行优化的,可以将归并排序的性能提升 10% – 15%

空间复杂度

归并排序的空间复杂度是 {O(N)},即需要额外的一个辅助数组来辅助两个有序子数组的合并。

稳定性

归并排序是一种稳定的排序算法。在合并两个有序的子数组时,当遇到两个相等的元素时,我们先取左边的元素,所以它们的相对位置不会改变。

写在最后

如果能把上面所讲到的都掌握,相信大家一定能在面试中表现不俗,面试的信心也来自于平时的积累。

总的来说,归并排序是一种很重要的排序算法。

首先他是面试中经常考察的一种经典算法,其次深刻的掌握其 自顶向下自底向上 的两种思想,对于我们深入理解分治和递归的算法思想是很有帮助的。

而且,在未来的文章中我们还会用到归并排序的思想来解决一些经典的算法题,大家拭目以待吧!

发表回复

后才能评论