一、归并
引入
假设现在的列表分两段有序,如何将其合并成为一个有序列表。
这种操作成为一次归并。
归并的思路
- 分别对两个列表进行遍历,比较两个列表中的最小值,将更小的取出来。
- 取出后一次进行上操作,直到其中一个列表中的元素被取完。
- 再直接将列一个列表中的剩下元素全部取出。
实现代码如下:
def merge(li, low, mid, high):
# 两个列表合并一块,最左边为low,最右边为high,第一个列表的最后一个元素下标为mid
# 则列表被分为两部分,一个为low - mid,另一个为mid+1 - high
# 最开始定义两个箭头 + 一个存放返回的空列表
i = low
j = mid +1
ltmp = []
while i<= mid and j <= high:
if li[i] < li[j]: # 此时i小,则将i对应的数取出,箭头向下移动一位
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# 当while执行完后必定是两部分中的一个没有剩余数字
while i <= mid: #对应左边的列表还有剩余
ltmp.append(li[i])
i += 1
while j <= high: #对应右边的列表还有剩余
ltmp.append(li[j])
j += 1
# 最后将数值返回li
li[low:high+1] = ltmp
li = [1,4,7,2,5,8]
print(li)
merge(li, 0, 2, 5)
print(li)
输出结果如下:
此时我们实现了将两个有序列表合并为一个有序列表。
二、归并排序的实现
大致分为三步:
- 分解:将列表越分越小,直至分成一个元素。
- 终止条件:一个元素是有序的
- 合并:将两个有序列表归并,列表越来越大。
代码的思路:主要运用了递归,对于整个无序列表,我们想要将其变为有序列表,主要采用以下三步:
- 确定好mid后,先将左边的排为有序
- 再将右边的拍为有序
- 最后采用上面提到的归并的思路,将两个有序的列表归并为一个列表。
def merge_sort(li, low, high):
if low < high:
mid = (low+high) // 2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
li = [1,4,7,2,5,8,3,6,9]
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
输出的结果如下:
因此,整个综合代码如下所示:
def merge(li, low, mid, high):
# 两个列表合并一块,最左边为low,最右边为high,第一个列表的最后一个元素下标为mid
# 则列表被分为两部分,一个为low - mid,另一个为mid+1 - high
# 最开始定义两个箭头 + 一个存放返回的空列表
i = low
j = mid +1
ltmp = []
while i<= mid and j <= high:
if li[i] < li[j]: # 此时i小,则将i对应的数取出,箭头向下移动一位
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# 当while执行完后必定是两部分中的一个没有剩余数字
while i <= mid: #对应左边的列表还有剩余
ltmp.append(li[i])
i += 1
while j <= high: #对应右边的列表还有剩余
ltmp.append(li[j])
j += 1
# 最后将数值返回li
li[low:high+1] = ltmp
def merge_sort(li, low, high):
if low < high:
mid = (low+high) // 2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
li = [1,4,7,2,5,8,3,6,9]
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
三、归并排序的复杂度
1. 时间复杂度
一次归并的时间复杂度为O(n),可以参考上图中的分解和合并考虑归并算法的时间复杂度。
每次进行的操作的复杂度为O(n),共有O(logn)层,因此总共的时间复杂度为O(nlogn)。
2. 空间复杂度
因为在merge中我们开辟了一个空间ltmp[],因此空间复杂度为O(n).
pyhton中的sort方法是基于归并排序的。