本文共 2640 字,大约阅读时间需要 8 分钟。
上一博文讲了如何使用归并排序进行一次排序即一次归并(列表分两段有序,将其合成为一个有序列表这种操作称为一次归并)
今天来讲讲,怎么利用归并排序将一个无序列表进行排序!# _*_coding:utf-8_*_'''TOPIC: 归并author: Bluetime: 2020-08-05QQ: 2458682080'''import random# 一次归并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_tempdef mergr_sort(li, low, high): if low < high: # 至少有两个元素,递归 mid = (low + high) // 2 mergr_sort(li, low, mid) # 1. 把左边排好序 mergr_sort(li, mid+1, high) # 2. 把右边排好序 merge(li, low, mid, high) # 3. 把左右归并li = list(range(10))random.shuffle(li)print(li)mergr_sort(li, 0, len(li)-1)print(li)
结果为:
[8, 6, 7, 9, 1, 2, 5, 0, 3, 4][0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
利用递归,将列表划分到最小单元进行排序,比如一个长度为10的无序列表:
由于过程较多,这里我只展示了前面几步的递归过程,但是理解了这几步过程,后面过程也就可以理解了。或者可以利用打印排序过程来帮助理解这个过程:
# _*_coding:utf-8_*_'''TOP: 归并author: Bluetime: 2020-08-05QQ: 2458682080'''import random# 一次归并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_temp# 查看每一次左右归并后的结果def mergr_sort_test(li, low, high): if low < high: # 至少有两个元素,递归 mid = (low + high) // 2 mergr_sort_test(li, low, mid) # 1. 把左边排好序 mergr_sort_test(li, mid+1, high) # 2. 把右边排好序 print(li[low: high+1]) merge(li, low, mid, high) print(li)li = list(range(10))random.shuffle(li)print(li)mergr_sort_test(li, 0, len(li)-1)print(li)
结果为:
[8, 7, 2, 5, 1, 3, 0, 6, 4, 9][8, 7][7, 8, 2, 5, 1, 3, 0, 6, 4, 9][7, 8, 2][2, 7, 8, 5, 1, 3, 0, 6, 4, 9][5, 1][2, 7, 8, 1, 5, 3, 0, 6, 4, 9][2, 7, 8, 1, 5][1, 2, 5, 7, 8, 3, 0, 6, 4, 9][3, 0][1, 2, 5, 7, 8, 0, 3, 6, 4, 9][0, 3, 6][1, 2, 5, 7, 8, 0, 3, 6, 4, 9][4, 9][1, 2, 5, 7, 8, 0, 3, 6, 4, 9][0, 3, 6, 4, 9][1, 2, 5, 7, 8, 0, 3, 4, 6, 9][1, 2, 5, 7, 8, 0, 3, 4, 6, 9][0, 1, 2, 3, 4, 5, 6, 7, 8, 9][0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
每层为n,有log(n)层,故时间复杂度为: O(nlog(n))
转载地址:http://wbiwi.baihongyu.com/