思路
**基本思路:**借助额外空间,合并两个有序数组,得到更长的有序数组
**算法思想:**分而治之(分治思想)。「分而治之」
动画演示
边想边写
- 将数组分割为不可再分状态
边想边写,一步一步的来
首要目标是,将当前数组分成两段(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个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同
经典问题
- 《剑指 Offer》第 51 题:数组中的逆序对,照着归并排序的思路就能写出来;
- 「力扣」第 315 题:计算右侧小于当前元素的个数,它们是一个问题。