归并排序

思路

**基本思路:**借助额外空间,合并两个有序数组,得到更长的有序数组

**算法思想:**分而治之(分治思想)。「分而治之」

动画演示

[中文字幕]3D动画演示合并(归并)排序VS快速排序

边想边写

  • 将数组分割为不可再分状态

边想边写,一步一步的来

首要目标是,将当前数组分成两段(left 和 right),循环此步骤直到不可再分

def merge_sort(arr):
    mid = len(arr) >> 1
    if len(arr) <= 1: # 当只有一个元素时,直接返回
        return arr
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # ...
  • 比较并合并
比较过程演示

每个数组都需要一个游标,用于记录当前的位置.

cur_l, cur_r = 0, 0

比较大小

res = [] # 用于保存此次合并结果
if left[cur_l] < right[cur_r]:
    res.append(left[cur_l])
    # 移动游标
    cur_l += 1
else:
    res.append(right[cur_r])
    cur_r += 1

上方只是比较一次,再套上一个循环,完整比较.

循环条件: len(left) < cur_l and len(right) < cur_r

其中一个数组的游标等于其长度,则退出循环

while len(left) < cur_l and len(right) < cur_r:
    res = [] # 用于保存此次合并结果
if left[cur_l] < right[cur_r]:
    res.append(left[cur_l])
    # 移动游标
    cur_l += 1
else:
    res.append(right[cur_r])
    cur_r += 1

循环退出后,有一个数组必定留有一个元素,没有被比较。 直接添加到 res 之后即可

res += left[cur_l:]
res += right[cur_r:]

完整代码

def merge_sort(arr):
    mid = len(arr) >> 1
    if len(arr) <= 1:
        return arr
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    res = []
    cur_l, cur_r = 0, 0
    while cur_l < len(left) and cur_r < len(right):
        if left[cur_l] <= right[cur_r]:
            res.append(left[cur_l])
            cur_l += 1
        else:
            res.append(right[cur_r])
            cur_r += 1
    res += left[cur_l:]
    res += right[cur_r:]
    return res

注意

实现归并排序的时候,要特别注意,不要把这个算法实现成非稳定排序,区别就在 <=<

        if left[cur_l] < right[cur_r]:
            res.append(left[cur_l])
            cur_l += 1

如果这里使用了 < ,那么下方的情况

left [1,2] 和 right [2, 3] 两个有序数组

当left[1] 与 right[0] 相比较时,相等,满足 if left[cur_l] <= right[cur_r]:

此时,right的2 会先于 left的2 合并, 也就是说,原本left的2在前面,现在left的2到了right的2后面

此时的 归并排序 就是不稳定的

怎么判断排序稳定:保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同

经典问题