概念

归并排序, 首先我们要了解什么是归并

归并

归并 可以总结为对多个有序列表有序合并.

比如针对两个有序列表如下

[15,9,4,1]
[98,76,14,7,5]

这两个有序列表合并后的结果是:

[98, 76, 15, 14, 9, 7, 5, 4, 1]

这个过程就是归并.

注意, 这里的列表一定先是有序列表, 方能进行归并,且结果也是有序列表

归并说明

针对两个有序列表 s1,s2, 如何进行归并,过程如下(这里均是倒序排列)

s1s2均从第0个元素开始比较, 假如s1的元素值小于s2的元素值,那么将s2的元素值置于一个临时列表s中,并将s2的偏移量向后移动一位, 同理, 假如s1的元素值大于s2的元素值,那么就将s1的元素值添加到临时列表s中,并将s1的偏移量向后移动一位,直到其中某个列表的偏移量越界,那么再将另一个列表的剩余元素直接添加到临时猎列表s

最终这个s 就是归并好的有序列表

归并实现

def merge(s1,s2):
    s1_index = 0
    s2_index = 0

    s1_len = len(s1)
    s2_len = len(s2)

    s = []
    while s1_index < s1_len and s2_index < s2_len:
        if s1[s1_index] < s2[s2_index]:
            s.append(s2[s2_index])
            s2_index += 1
        else:
            s.append(s1[s1_index])
            s1_index += 1
    if s1_index == s1_len:
        s += s2[s2_index:]
    elif s2_index == s2_len:
        s += s1[s1_index:]
    return s

测试一下

s1 = [15,9,4,1]
s2 = [98,76,14,7,5]

print(merge(s1,s2))

结果如下

[98, 76, 15, 14, 9, 7, 5, 4, 1]

归并排序

讲完了归并, 我们就该说归并排序了,针对一个无序的列表,我们可以将其分割成两两一组的小列表,将每组的这两个小列表进行归并, 这样我们就将原本的列表分成了一个个小的有序列表的集合, 然后我们再对这个集合做分组归并。 通过这种方式将一个大的无序列表分治处理,从而得到最终的排序结果

实现

def merge_sort(s):
    s_len = len(s)
    if s_len < 2:
          #只有一个有序列表时即表示排序完成, 返回结果
        return s[0]

    index = 0
    x = []
    while index < s_len:
        if index < (s_len - 1): 
            #如果能两两分组,进行归并
            x.append(merge(s[index],s[index+1]))
        else:
            #(奇数个元素时),最后的单个元素直接添加
            x.append(s[index])
        index += 2
    return merge_sort(x) #递归处理

测试

x = [128,299,992,2,3,8,3,200,55,18,9,89,43,76,0,-1,-786,343,-65]

在向merge_sort传递参数前, 要将参数列表元素做列表化处理,因为每次归并时都是针对列表做处理的,实际的调用如下

x = [128,299,992,2,3,8,3,200,55,18,9,89,43,76,0,-1,-786,343,-65]
m = [[n] for n in x]
print(merge_sort2(m))

结果如下

[992, 343, 299, 200, 128, 89, 76, 55, 43, 18, 9, 8, 3, 3, 2, 0, -1, -65, -786]
right