归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。
将数组分解最小之后,依次合并两个有序数组。基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位;然后再比较,直至一个数组为空,最后把另一个数组的剩余部分追加。
归并排序的分析
快速排序传入本身列表,通过控制操作范围达成排序目的
归并排序则传入原序列切片后生成的新的子序列
def merge_sort(alist):
'''归并排序'''
'''对列表进行拆分'''
n = len(alist)
# 1.先将列表进行拆分,直至拆分到每个分组只有一个元素
if n <= 1: # 递归终止条件
return alist # 当序列只有一个值时无需排序,直接返回序列本身
else:
mid = n // 2
# 此时将列表分成两个部分
left_li = merge_sort(alist[mid:]) # 对拆分后的部分再调用归并排序,返回left_li和right_li是有序的新列表
right_li = merge_sort(alist[:mid])
'''对列表进行合并'''
left_pointer, right_pointer = 0, 0
# 2.将两个有序的子序列,合并成一个新的整体
result = [] # 子序列合并后为一新列表,建一个空列表用于存储
while left_pointer < len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] <= right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1
# 当退出循环体时,左右两个部分至少有一个指针已遍历完,则在整体后追加另一边游标未处理的剩余数据
result.extend(left_li[left_pointer:]) # 列表.extend(列表),直接在原对象上追加新列表,不生成新对象占用空间
result.extend(right_li[right_pointer:]) # 对一个列表,当超出列表长度进行切片,则返回一个空列表,不报错
return result # 返回新对象result
测试
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55]
print(li)
sorted_li = merge_sort(li) # 归并排序的返回值为一个已排序的新列表,不对原列表本身排序
print(li)
print(sorted_li)
执行结果:
[54, 26, 93, 17, 77, 31, 44, 55]
[54, 26, 93, 17, 77, 31, 44, 55]
[17, 26, 31, 44, 54, 55, 77, 93]
归并函数代码执行顺序
缩进代表在一个递归函数内
1.merge_sort([54, 26, 93, 17, 77, 31, 44, 55])
# 运行到left_li = merge_sort(alist[mid:])
2.left1_li = merge_sort([54, 26, 93, 17]) # 递归函数,打开下层函数搁置一边
3.left2_li = merge_sort([54, 26])
4.left3_li = merge_sort([54]) # 再调用函数时,得到第一个返回值[54]
# 回到上一步搁置代码处,继续执行该循环体中的下行代码:right_li = merge_sort(alist[:mid])right2_li = merge_sort([54,26][1:])
5.right3_li = merge_sort([26]) # 返回值[26],关闭最里层递归函数
6.result = [26, 54] # 此时merge_sort([54, 26])继续执行向下执行result循环体部分,进行合并
7.right2_li = merge_sort([93, 17])
8.left3_li = merge_sort([93])
9.right3_li = merge_sort([17])
10.result = [17, 93]
11.result = [17, 26, 54, 93]
12.right_li = merge_sort([77, 31, 44, 55])
13.left2_li = merge_sort([77, 31])
14.left3_li = merge_sort([77])
15.right3_li = merge_sort([31])
16.result = [31, 77]
17.right2_li = merge_sort([44, 55])
18.left3_li = merge_sort([44])
19.right3_li = merge_sort([55])
20.result = [44, 55]
21.result = [31, 44, 55, 77]
22.result = [17, 20, 26, 31, 44, 54, 55, 77, 93]
时间复杂度
归并排序代码,对序列的拆分是顺序结构时间复杂度为O(1)。进入合并部分代码后为循环体层级数与层级做乘法运算;每一层级级合并都是顺序执行的,对应的时间复杂度做加运算。每一级数据的合并都要经过两两之间条件对比,时间复杂度为O(n);合并的层级次数2^x=n,即x=log2(n),时间复杂度O(logn)。
与快速排序不同对归并排序,永远从中轴线开始拆分,不存在分割线严重偏离的情况,所以最坏时间复杂度还是O(nlogn)。
通过条件if left_li[left_pointer] <= right_li[right_pointer],考虑等号可以确保排序的稳定性。
整体时间复杂度O(nlogn)
- 最优时间复杂度:O(nlogn)
- 最坏时间复杂度:O(nlogn)
- 稳定性:稳定
归并排序是冒泡、选择、插入、希尔、快速这些排序中最坏时间复杂度最小的,最坏时间复杂度为O(nlogn)。但归并排序返回的是一个排序后的新列表,占用了两份列表空间(原无序列表+新有序列表)。
常见排序算法效率比较
至少会写3种排序算法,快速排序常用必需会!
快速排序平均时间复杂度为O(nlogn),且不需要额外的存储空间。