python 归并排序（Merge Sort）

归并排序（Merge Sort）

归并排序是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的基本思想是：将数组递归地分成两半，分别对两半进行排序，然后将排序后的两半合并成一个有序数组。

归并排序的步骤：

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

时间复杂度：

• 最坏情况：O(n log n)
• 最好情况：O(n log n)
• 平均情况：O(n log n)

空间复杂度：

• O(n) —— 需要额外的空间来存储合并后的数组。

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

# 示例使用
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)

输出结果

排序后的数组: [3, 9, 10, 27, 38, 43, 82]

归并排序的详细过程

以数组 [38, 27, 43, 3, 9, 82, 10] 为例：

1. 分解：

   • 将数组分成 [38, 27, 43, 3] 和 [9, 82, 10]。
   • 继续分解：
     • [38, 27, 43, 3] 分成 [38, 27] 和 [43, 3]。
     • [9, 82, 10] 分成 [9] 和 [82, 10]。
   • 继续分解：
     • [38, 27] 分成 [38] 和 [27]。
     • [43, 3] 分成 [43] 和 [3]。
     • [82, 10] 分成 [82] 和 [10]。

2. 排序：

   • 每个子数组只有一个元素，本身已经有序。

3. 合并：

   • 合并 [38] 和 [27] 得到 [27, 38]。
   • 合并 [43] 和 [3] 得到 [3, 43]。
   • 合并 [27, 38] 和 [3, 43] 得到 [3, 27, 38, 43]。
   • 合并 [9] 和 [10, 82] 得到 [9, 10, 82]。
   • 合并 [3, 27, 38, 43] 和 [9, 10, 82] 得到 [3, 9, 10, 27, 38, 43, 82]。

归并排序的优缺点

优点：

• 时间复杂度稳定为 O(n log n)，性能优异。
• 是稳定的排序算法（相同元素的相对位置不变）。
• 适用于链表等非连续存储结构。

缺点：

• 需要额外的存储空间，空间复杂度为 O(n)。
• 对于小规模数据，性能可能不如插入排序等简单算法。

归并排序的适用场景

• 需要稳定排序的场景。
• 数据规模较大。
• 适用于链表等非连续存储结构。

优化归并排序

1. 小数组使用插入排序：

   • 当数组规模较小时，插入排序的效率更高。

2. 原地归并排序：

   • 通过复杂的实现，可以减少额外的存储空间，但会增加代码复杂度。

优化后的归并排序实现

def merge_sort_optimized(arr):
    if len(arr) <= 10:  # 小数组使用插入排序
        return insertion_sort(arr)
    
    mid = len(arr) // 2
    left_half = merge_sort_optimized(arr[:mid])
    right_half = merge_sort_optimized(arr[mid:])
    
    return merge(left_half, right_half)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 示例使用
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort_optimized(arr)
print("优化后的排序数组:", sorted_arr)

总结

归并排序是一种高效且稳定的排序算法，适用于大规模数据的排序。通过优化策略，可以进一步提高其性能。