python写归并排序

python写归并排序

开始今天内容之前，先给大家推荐一款审核利器，goinception，下载地址:

http://218.206.242.148:12345/images/20_tencent/20220917/rltykju12m2 自从inception闭源之后，对于SQL审核的工具都是各家开发定制各自的，这个项目goinception的审核结果和inception几乎相同，大家可以作为参考，看看是否可以直接拿来定制自己的审核工具。

回来比较晚了，写点python程序吧，python实现归并排序。

归并排序大家可能都不陌生，它的主要逻辑如下：

1、将一个序列拆分为两个序列

2、将这两个子序列按照第一步的方法再进行拆分

3、等到所有的序列都拆分为1个元素的时候，再两两进行排序，合并成一个有序序列即可。

整个排序思路，有一个先分再合的过程，如下：

# 这个函数用来将两个有序序列合并成一个有序序列
def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1
    # 如果某个序列被合并完毕，则补齐另外一个序列的剩余值即可
    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)//2
    # 进行拆分
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right) #递归的思路


if __name__ == '__main__':
    a = [10,14,33,2,39,8,41]
    print (merge_sort(a))

运行结果如下：

[2, 8, 10, 14, 33, 39, 41]

Process finished with exit code 0

执行时间复杂度：N*logN

有帮助的话还希望点下再看哈