导语:
本文主要介绍了关于python归并排序的实现原理的相关知识,希望可以帮到处于编程学习途中的小伙伴
原理分析
1、把一个序列从中间位置分成两个序列;
2、把这两个子序列按第一步继续分成两部分;
3.直到所有子序列的长度都为1,也就是说不能再有二元截断。这时,这些对被合并成一个有序的序列。
实例
def merge(arr, low, mid, high):
# low 和 high 为整个数组的第一个和最后一个位置索引,mid 为中间位置索引
# i 和 j 为指针,最初位置分别为两个有序序列的起始位置
# ltmp 用来存放合并后的序列
i = low
j = mid+1
ltmp = []
while i <= mid and j <= high: # 只要左右两边都有数
if arr[i] < arr[j]: # 当左边的数小于右边的数
ltmp.append(arr[i]) # 将左边的数存入 ltmp
i += 1 # 左边的指针往右移一位
else: # 当右边的数小于左边的数
ltmp.append(arr[j]) # 将右边的数存入 ltmp
j += 1 # 右边的指针往右移一位
# 上面的 while 语句执行完后,左边或者右边没有数了
while i <= mid: # 当左边还有数的时候
ltmp.append(arr[i]) # 将左边剩下的数全部存入 ltmp
i += 1
while j <= high: # 当右边还有数的时候
ltmp.append(arr[j]) # 将右边剩下的数全部存入 ltmp
j += 1
arr[low:high+1] = ltmp # 将排序后的数组写回原数组
def merge_sort(arr, low, high): # low 和 high 为整个数组的第一个和最后一个位置索引
if low < high: # 至少有两个元素
mid = (low + high) // 2
merge_sort(arr, low, mid) # 把左边递归分解
merge_sort(arr, mid+1, high) # 把右边递归分解
merge(arr, low, mid, high) # 做归并
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
你可能也喜欢
- ♥ 如何用python for语句打印乘法表?10/12
- ♥ 2020学python好还是php好?01/09
- ♥ 如何在python中编写不重复的随机数09/12
- ♥ 分分钟带你用Python绘图库画一个python11/03
- ♥ python中的不等号是什么09/20
- ♥ 工作很乏味?试试 Python 循环语句(for 循环)01/10
内容反馈