关于算法:MergeSort-归并排序│算法与数据结构

家喻户晓，以元素之间进行比拟的形式进行排序的算法，在工夫复杂度上最低也只能是 O(nlog^n)，归并排序算法的工夫复杂度就是 O(nlog^n)。

归并排序是分治策略的一个典型利用。分治策略就是将大的问题进行屡次宰割，生成多个小的子问题，直到宰割成最小单位。这些小问题是能够轻松解决的，递归合并已解决的小问题，最终解决原问题。

归并排序就是按照分治策略，将一个无序的序列屡次宰割，直到每个子序列都是最小单位(只有一个元素或空序列)，这些子序列都能够被当作有序序列。这时针对子序列的排序问题解决了，那么只须要留神在递归合并这些子序列时，合并生成的子序列也是有序的，最终失去的后果就必然是一个有序序列。思路清晰了，具体要怎么做呢?

分

假如当初有一个由八个元素组成的序列，这八个元素的大小排列程序是凌乱的。依据分治策略，能够把这个序列一分为二，这样就分成了两个由四个元素组成的子序列。

然而这两个子序列仍旧无奈轻而易举的解决排序问题，那就持续宰割，再次宰割后失去了四个由两个元素组成的子序列，而后再次宰割，宰割成八个由一个元素组成的子序列。这时，每个子序列中只有一个元素，这也必然是有序的，那么子序列的排序问题解决了，分这一步也就完结了。

合

八个由一个元素组成的有序序列两两合并，合并成四个由两个元素组成的有序序列，再次进行两两合并，直到合并成一个由八个元素组成的有序序列，问题解决。

说的轻轻松松，两个只有一个元素的有序序列合并成一个有序序列非常简单，比照它们中的那个惟一的元素即可，然而有多个元素的有序序列之间如何合并成一个大的有序序列呢?

让咱们先抛开之前讲述的例子，来到一个新的例子背后。假如有两个有序序列，须要把这两个有序序列合并成一个有序序列。

如上图，能够设想成两个人各持有一个有序序列进行游戏，两个人别离从本人持有的序列中拿出一个最小值的元素作为手牌，比照手牌大小，较小的一方就要将手牌抛弃到坟场中，而后从持有的序列中再拿出一个最小值的元素退出手牌。直到某一方失去全副元素，另一方将手中残余的元素按程序抛弃到坟场中。在游戏中，元素退出到坟场中的程序是从最小到最大，如果将坟场了解为一个序列，那么当初就失去了一个合并后的有序序列。

如果将以上的排序办法整合到归并排序中，那么归并排序剩下的两个由多个元素组成的有序序列合并成一个有序序列的问题就解决了。

代码

归并排序的原理和问题都已解决，上代码:

def 归并排序(unsort_list):
    '''子序列的元素数为 1 或者是空序列时, 子序列主动成为有序序列, 间接返回子序列'''
    if len(unsort_list) <= 1:
        return unsort_list
    '''将序列 (元素数大于 1) 一分为二'''
    中值索引 = int(len(unsort_list) / 2)
    左序列 = 归并排序(unsort_list[: 中值索引])
    右序列 = 归并排序(unsort_list[中值索引:])
    '''两个有序序列合并成一个有序序列'''
    左指针, 右指针, 指针, 左边界, 右边界 = 0, 0, 0, len(左序列), len(右序列)
    while (左指针 < 左边界) or (右指针 < 右边界):  # 任何一个子序列的指针未达到边界, 就继续执行
        if (右指针 < 右边界) and ((左指针 >= 左边界) or (左序列[左指针] >= 右序列[右指针])):
            # 如果左边未达到边界, 持续判断; 右边达到边界 或者 右边第一个元素大于左边第一个元素, 左边小, 进入主列表
            unsort_list[指针] = 右序列[右指针]
            右指针, 指针 = 右指针 + 1, 指针 + 1
        if (左指针 < 左边界) and ((右指针 >= 右边界) or (右序列[右指针] > 左序列[左指针])):
            # 如果右边未达到边界, 持续判断; 左边达到边界 或者 左边第一个元素大于右边第一个元素, 右边小, 进入主列表
            unsort_list[指针] = 左序列[左指针]
            左指针, 指针 = 左指针 + 1, 指针 + 1
    return unsort_list


if __name__ == "__main__":
    print(归并排序([6, 3, 2, 7, 1, 5, 8, 4]))

在上述代码中，while 语句局部的代码段中的判断都合并在了一起，很不好了解，须要破费工夫去整顿思路，其实能够将这些判断全副拆分进去，这样更简略的去了解归并排序:

'''注: 这里仅写了 while 语句局部的代码, 其余局部的代码段雷同'''

def 归并排序(unsort_list):
    # 省略

    '''两个子序列都有未比拟的元素, 任意一个子序列的指针达到边界, 都会完结此循环'''
    左指针, 右指针, 指针, 左边界, 右边界 = 0, 0, 0, len(左序列), len(右序列)
    while (左指针 < 左边界) and (右指针 < 右边界):
        if 左序列[左指针] > 右序列[右指针]:  # 比元素的值的大小, 留神指针的挪动
            unsort_list[指针] = 右序列[右指针]
            右指针 += 1
        else:
            unsort_list[指针] = 左序列[左指针]
            左指针 += 1
        指针 += 1
    '''这时必有一个子序列的指针达到边界, 另一个子序列的指针未达到边界, 将这个子序列残余的元素退出到合并序列中'''
    while 左指针 < 左边界:
        unsort_list[指针] = 左序列[左指针]
        左指针 += 1
        指针 += 1
    while 右指针 < 右边界:
        unsort_list[指针] = 右序列[右指针]
        右指针 += 1
        指针 += 1

    # 省略

参考资料

• 视频《清华大学邓俊辉数据结构与算法【完】》

公众号 :「python 库详解」，专一于 python 规范库与 python 第三方库的解析教程，以及其余 python 的相干内容。挖掘更多原创文章，期待您的关注。