DSA 归并排序

归并排序

归并排序算法是一种分治算法，它通过先将数组分解成更小的数组，然后以正确的方式将数组重新组合在一起，从而对数组进行排序。

分治： 该算法首先将数组分解成越来越小的部分，直到其中一个子数组只包含一个元素。

合并： 该算法通过将最小值放在最前面，将小的数组部分合并在一起，从而生成一个排序后的数组。

分解和组合数组以对数组进行排序是递归进行的。

在上面的动画中，每次条形图向下移动都代表一个递归调用，将数组分成更小的部分。 当条形图向上移动时，意味着两个子数组已经合并在一起。

归并排序算法可以这样描述

看看下面的图，从不同的角度了解归并排序是如何工作的。 如你所见，数组被分成越来越小的部分，直到合并在一起。 并且在合并时，会比较每个子数组的值，以便最小值排在最前面。

手动运行过程

让我们尝试手动进行排序，以便在实际用编程语言实现它之前，更好地理解归并排序的工作原理。

步骤 1： 我们从一个未排序的数组开始，我们知道它会分成两半，直到子数组只包含一个元素。 归并排序函数调用自身两次，一次针对数组的每一半。 这意味着第一个子数组将首先分解成最小的部分。

步骤 2： 第一个子数组的分解已完成，现在是合并的时候了。 8 和 9 是要合并的第一个元素。 8 是最小值，所以它排在 9 之前，形成第一个合并后的子数组。

步骤 3： 要合并的下一个子数组是 [ 12] 和 [ 8, 9]。 比较两个数组中的值，从开头开始。 8 小于 12，所以 8 排在前面，9 也小于 12。

步骤 4： 现在，第二个大的子数组被递归地拆分。

步骤 5： 3 和 11 合并在一起，顺序和它们显示的顺序相同，因为 3 小于 11。

步骤 6： 值为 5 和 4 的子数组被拆分，然后合并在一起，使得 4 排在 5 之前。

步骤 7： 合并右边的两个子数组。 进行比较以创建新合并后的数组元素

1. 3 小于 4
2. 4 小于 11
3. 5 小于 11
4. 11 是最后一个剩余值

步骤 8： 合并最后两个剩余的子数组。 让我们详细看看如何进行比较以创建新的合并后的已完成的排序数组

3 小于 8

步骤 9： 4 小于 8

步骤 10： 5 小于 8

步骤 11： 8 和 9 小于 11

步骤 12： 11 小于 12

排序完成！

运行下面的模拟，查看上面步骤的动画效果

{{ x.dieNmbr }}

手动运行过程：发生了什么？

我们看到该算法有两个阶段：首先是拆分，然后是合并。

虽然可以不用递归实现归并排序算法，但我们将使用递归，因为这是最常见的方法。

我们在上面的步骤中看不到，但为了将数组拆分成两半，数组的长度除以 2，然后向下取整以获得一个称为“mid”的值。 此“mid”值用作拆分数组的索引。

数组被拆分后，排序函数用每一半调用自身，以便数组可以递归地再次拆分。 当子数组只包含一个元素时，拆分停止。

在归并排序函数结束时，子数组被合并，以便在重建数组时，子数组始终处于排序状态。 为了合并两个子数组，使结果排序，比较每个子数组的值，并将最小值放入合并后的数组中。 之后，比较两个子数组中的下一个值，并将最小值放入合并后的数组中。

归并排序实现

为了实现归并排序算法，我们需要

1. 一个包含需要排序的值的数组。
2. 一个函数，它接受一个数组，将其拆分成两半，并用每一半调用自身，以便数组递归地不断拆分，直到子数组只包含一个值。
3. 另一个函数，它以排序的方式将子数组合并在一起。

生成的代码如下所示

def mergeSort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    leftHalf = arr[:mid]
    rightHalf = arr[mid:]

    sortedLeft = mergeSort(leftHalf)
    sortedRight = mergeSort(rightHalf)

    return merge(sortedLeft, sortedRight)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)

在第 6 行，arr[:mid] 获取数组中直到但不包括索引“mid”上的值的所有值。

在第 7 行，arr[mid:] 获取数组中从索引“mid”上的值开始的所有值以及后面的所有值。

在第 26-27 行，完成了合并的第一部分。 在此，比较两个子数组的值，并且左子数组或右子数组为空，因此可以用左子数组或右子数组中剩余的值填充结果数组。 这些行可以互换，结果相同。

非递归归并排序

由于归并排序是一种分治算法，递归是最直观的实现代码。 归并排序的递归实现可能更容易理解，而且通常使用更少的代码行。

但是归并排序也可以不用递归实现，这样就不需要函数调用自身。

看看下面的归并排序实现，它不使用递归

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

def mergeSort(arr):
    step = 1  # Starting with sub-arrays of length 1
    length = len(arr)
    
    while step < length:
        for i in range(0, length, 2 * step):
            left = arr[i:i + step]
            right = arr[i + step:i + 2 * step]
            
            merged = merge(left, right)
            
            # Place the merged array back into the original array
            for j, val in enumerate(merged):
                arr[i + j] = val
                
        step *= 2  # Double the sub-array length for the next iteration
        
    return arr

unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)

你可能会注意到，上面的两个归并排序实现中的合并函数完全相同，但在上面的实现中，mergeSort 函数内部的 while 循环用于替换递归。 while 循环在原地进行数组的拆分和合并，这使得代码有点难以理解。

简单来说，mergeSort 函数中的 while 循环使用较短的步长来对初始数组的微小部分（子数组）进行排序，使用的是 merge 函数。然后，步长会逐渐增加，合并并排序数组的更大部分，直到整个数组排序完成。

归并排序时间复杂度

有关时间复杂度的一般解释，请访问 此页面。

有关归并排序时间复杂度的更详细解释，请访问 此页面。

归并排序的时间复杂度为

\[ O( n \cdot \log n ) \]

对于不同类型的数组，时间复杂度几乎相同。无论数组已经排序还是完全打乱，该算法都需要将数组拆分并重新合并。

下图显示了归并排序的时间复杂度。

在下面的模拟中运行不同数量的数组值，看看归并排序对包含 \(n\) 个元素的数组所需的运算次数是 \(O(n \log n)\)

如果我们保持值的数量 \(n\) 不变，则“随机”、“降序”和“升序”所需的运算次数几乎相同。

归并排序在每次执行时几乎都相同，因为数组会被拆分并使用比较进行合并，无论数组是否已经排序。