个人技术博客地址：http://songmingyao.com/
原理
- 将递归分解列表，直至最小（即每个列表仅有一个元素）
- 将列表分解最小之后，递归合并两个列表，即挨个比较两个列表中最前面的元素，谁较小就将谁加入新的列表，而后该列表的下标后移一位，继续比较，直至其中一个列表为空，而后将另一个列表中剩余的元素加入新列表
- 不断合并，直至完全排序完成
源码
def merge_sort(l):
# 对列表进行二分分解
n = len(l)
if n <= 1:
return l
mid_posi = n//2
# print(1)
l_list = merge_sort(l[:mid_posi])
# print(2)
r_list = merge_sort(l[mid_posi:])
# print(3)
# 对列表进行合并
sorted_list = []
l_posi = 0
r_posi = 0
# print('l_list: %s' % l_list)
# print('r_list: %s' % r_list)
while l_posi < len(l_list) and r_posi < len(l_list):
if l_list[l_posi] <= r_list[r_posi]:
sorted_list.append(l_list[l_posi])
l_posi += 1
else:
sorted_list.append(r_list[r_posi])
r_posi += 1
# 将列表剩余部分合并
sorted_list += l_list[l_posi:]
sorted_list += r_list[r_posi:]
# print('sorted_list: %s' % sorted_list)
return sorted_list
if __name__ == '__main__':
l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
print(l)
sorted_list = merge_sort(l)
print(sorted_list)
时间复杂度
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定
