跳到主要内容

归并排序

归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的思想。它将一个数组分成两个子数组，分别对子数组进行排序，然后将排序后的子数组合并成一个有序的数组。归并排序的时间复杂度为 O(n log n)，是一种稳定的排序算法。

归并排序的基本思想​

归并排序的核心思想可以概括为以下三个步骤：

  1. 分解：将数组递归地分成两个子数组，直到每个子数组只包含一个元素。
  2. 排序：对每个子数组进行排序（由于子数组只有一个元素，它本身已经是有序的）。
  3. 合并：将两个有序的子数组合并成一个有序的数组。
提示

归并排序的关键在于合并操作。合并两个有序数组的过程是线性的，时间复杂度为 O(n)。

归并排序的实现​

下面是一个用 Python 实现的归并排序算法：

python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 分解：将数组分成两个子数组
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    # 合并：将两个有序子数组合并
    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0
    
    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1
    
    # 将剩余的元素添加到结果中
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])
    
    return sorted_array

示例​

假设我们有一个数组 [38, 27, 43, 3, 9, 82, 10]，以下是归并排序的执行过程：

  1. 分解：

    • 将数组分成 [38, 27, 43, 3] 和 [9, 82, 10]。
    • 继续分解，直到每个子数组只有一个元素。

  2. 合并：

    • 将 [38] 和 [27] 合并为 [27, 38]。
    • 将 [43] 和 [3] 合并为 [3, 43]。
    • 将 [27, 38] 和 [3, 43] 合并为 [3, 27, 38, 43]。
    • 类似地，对右半部分进行合并，最终得到 [3, 9, 10, 27, 38, 43, 82]。

输入和输出​

python
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 输出: [3, 9, 10, 27, 38, 43, 82]

归并排序的时间复杂度​

归并排序的时间复杂度为 O(n log n)，其中：

  • 分解：每次将数组分成两半，需要 O(log n) 次分解。
  • 合并：每次合并操作需要 O(n) 的时间。

因此，总的时间复杂度为 O(n log n)。

备注

归并排序的空间复杂度为 O(n)，因为需要额外的空间来存储合并后的数组。

归并排序的实际应用​

归并排序在以下场景中非常有用：

  1. 大数据排序：当数据量较大时，归并排序的高效性使其成为首选算法。
  2. 外部排序：当数据无法全部加载到内存时，归并排序可以分块处理数据。
  3. 链表排序：归并排序是链表排序的最佳选择之一，因为它不需要随机访问元素。

总结​

归并排序是一种高效且稳定的排序算法，适用于大规模数据的排序。它的核心思想是分治法，通过递归地将数组分解成更小的子数组，然后合并这些子数组来实现排序。虽然归并排序需要额外的空间，但其时间复杂度的优势使其在实际应用中非常受欢迎。

附加资源与练习​

  1. 练习：尝试用你熟悉的编程语言实现归并排序，并测试其性能。
  2. 深入学习：了解其他分治算法，如快速排序和二分查找。
  3. 扩展阅读：研究归并排序在外部排序中的应用，例如处理大型文件时的排序方法。
警告

在实现归并排序时，注意处理边界条件，例如空数组或只有一个元素的数组。