本文共 723 字,大约阅读时间需要 2 分钟。
假设现在的列表分两段有序,将其合成为一个有序列表这种操作称为一次归并
原理很简单,代码也很简单:
author: Bluetime: 2020-08-05QQ: 2458682080'''# 现在的列表分两段有序,将其合成为一个有序列表def merge(li, low, mid, high): i = low j = mid + 1 li_temp = [] while i <= mid and j <= high: # 只要左右两边都有数 if li[i] < li[j]: li_temp.append(li[i]) i += 1 else: li_temp.append(li[j]) j += 1 # while执行完,肯定有一部分没数了 while i <= mid: # 左边有数,右边没数 li_temp.append(li[i]) i += 1 while j <= high: # 右边有数,左边没数 li_temp.append(li[j]) j += 1 li[low: high+1] = li_templi = [2, 4, 5, 7, 1, 3, 6, 8]merge(li, 0, 3, 7)print(li)
结果为:
[1, 2, 3, 4, 5, 6, 7, 8]
该算法相当于把整个列表遍历了一遍进行交换,因此时间复杂度为: O(n)
转载地址:http://gfiwi.baihongyu.com/