归并排序

8.1 归并排序的定义

归并排序 (Merge Sort) 是一种高效、稳定的比较排序算法，采用“分而治之”的策略来排序元素。算法将数组分成两半，递归地排序每一半，然后合并排序好的两半，形成一个排序后的数组。

工作原理：

分割：

• 将原始数组分成两半，得到两个子数组。
• 对每个子数组重复该过程，直到每个子数组成为一个单独元素的数组（或为空）。

合并：

• 将两个相邻的子数组合并成一个排序数组。
• 重复合并过程，直到得到一个排序的数组。

归并排序的时间和空间复杂度

时间复杂度：

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

空间复杂度：

O(n) — 需要额外的内存来存储临时子数组。

8.2 自顶向下的归并法

原始序列递归地分成两半，直到得到一个元素的子序列。再通过合并方法从这些子序列形成有序对，然后是有序四个元素，以此类推。

来看一个序列：

把序列分成两半（递归地，直到得到对）。

每个子序列用合并方法排序，得到完整的排序序列。

8.3 归并排序算法的实现

这时候我们就要用到递归啦！和之前的算法比起来，这个算法很好又快速。它把数组分成两半，分别排序，然后把排好序的部分快速合并。

实现大概长这样：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到数组的中间位置
        left_half = arr[:mid]  # 将数组分成两个子数组
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 递归地排序左半部分
        merge_sort(right_half)  # 递归地排序右半部分
        
        i = j = k = 0
        
        # 合并已排序的部分
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # 检查是否有剩余元素
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

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

关键在最开始的地方：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到数组的中间位置
        left_half = arr[:mid]  # 将数组分成两个子数组
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 递归地排序左半部分
        merge_sort(right_half)  # 递归地排序右半部分

这里发生了什么：

1. 我们找到数组的中间位置
2. 将数组分成两部分
3. 分别对每一部分进行排序

这种方法可以大大加快算法速度。