1.简介

在本问中,我们将了解归并排序(Merge Sort)算法及其在Java中的实现。

归并排序是最有效的排序技术之一,它基于“分而治之”范式。

2.算法

归并排序是一种“分而治之”的算法,其中,我们首先将问题分解为子问题。

当子问题的解决方案准备就绪时,我们将它们组合在一起以获得最终的解决方案。

这是可以使用递归轻松实现的算法之一,因为我们处理子问题而不是主要问题。

该算法可以描述为以下两步过程:

  • 分割

    在这一步中,我们将输入数组分为两半,枢轴为数组的中点。对所有的半个数组递归执行此步骤,直到没有更多的半个数组可分割为止。

  • 集成

    在这一步中,我们从下到上对合并的数组进行排序和合并,并获得排序后的数组。

下图显示了数组{10,6,8,5,7,7,3,4}的完整合并排序过程。

如果我们仔细观察一下该图,我们可以看到将数组递归地分为两半,直到大小变为1。一旦大小变为1,合并过程开始起作用,并在排序时开始合并数组:

mergesort1

3. 实现

对于实现,我们将编写一个mergeSort函数,该函数将输入数组及其长度作为参数。

这将是一个递归函数,因此我们需要基本条件和递归条件。

基本条件检查数组长度是否为1,它将返回。在其余情况下,将执行递归调用。

对于递归情况,我们获得中间索引并创建两个临时数组l []r []。然后继续递归。

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];
 
    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);
 
    merge(a, l, r, mid, n - mid);
}

最后,我们调用合并函数,该函数接受要排序的数组和两个子数组以及两个子数组的开始索引和结束索引。

合并函数由两个子数组的元素进行比较,较小元素放到输入数组。

当我们到达一个子数组的末尾时,另一个数组中的其余元素将被复制到输入数组中,从而得到最终的排序数组:

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
  
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

我们来测试一下:

@Test
public void test_MergeSort() {
  int[] actual = { 5, 1, 6, 3, 2, 4 };
  int[] expected = { 1, 2, 3, 4, 5, 6 };
  MergeSort.mergeSort(actual, actual.length);
  assertArrayEquals(expected, actual);
}

4.复杂度

由于归并排序是一种递归算法,因此时间复杂度可以表示为以下递归关系

T(n) = 2T(n/2) + O(n)
  • 2T(n/2) 对应于对子数组进行排序所需的时间
  • O(n) 对应于合并整个数组的时间。

时间复杂度将变为O(nLogn)。

对于最坏,平均和最佳情况,这都是正确的,因为它将始终将数组分为两个然后合并。

当我们在每个递归调用中创建临时数组时,该算法的空间复杂度为O(n)

5. 总结

在本快速教程中,我们了解了归并排序算法的工作原理以及如何在Java中实现它。

与往常一样,可以在GitHub上获得代码示例。