python实现归并排序-蒲公英云

python实现归并排序

末蓝、 2022-11-02 11:55 339阅读 0赞

归并排序
“归并”是将两个或者两个以上的有序表组成一个新的有序表。假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为一，然后两两归并，得到n//2个长度为2或1的有序表；再两两归并，…直到合并成一个长度为n的有序表为止，这种方法称为2-路归并排序。
在这里插入图片描述
归并算法动态实现：

实现代码如下：

#merge的功能是将前后相邻的两个有序表归并为一个有序表的算法。
def merge(left, right):
    ll, rr = 0, 0
    result = []
    while ll < len(left) and rr < len(right):
        if left[ll] < right[rr]:
            result.append(left[ll])
            ll += 1
        else:
            result.append(right[rr])
            rr += 1
    result+=left[ll:]
    result+=right[rr:]
    return result
def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    num = len(alist) // 2   # 从中间划分两个子序列
    left = merge_sort(alist[:num]) # 对左侧子序列进行递归排序
    right = merge_sort(alist[num:]) # 对右侧子序列进行递归排序
    return merge(left, right) #归并
tesl=[1,3,45,23,23,12,43,45,33,21]
print(merge_sort(tesl))
#[1, 3, 12, 21, 23, 23, 33, 43, 45, 45]