一文看懂归并排序 python实现

红太狼 2021-05-10 11:33 596阅读 0赞

首先假设我们要排序的是这么一个序列a：

![20190327215212768.png][]

然后首先把它在中间“劈开”，分为两段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70][]

其中L=0；R=len(a)-1;M=len(a)//2;

把分好的这两个序列编号 ，建立两个指针i和j，都从各自的序列的第一个元素开始。然后建立一个空的列表b:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 1][]

然后比较left\[i\]和right\[j\]的大小，把小的那一个加到列表b里。然后i=i+1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 2][]

再比较left\[i\]和right\[j\]的大小，然后此处是right\[j\]大，所以right\[j\]放入列表b，j=j+1;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 3][]

然后依次把left和right的元素加入到b中，完成排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 4][]

那么问题来了，left和right明显是排序好的分数组，如果我要排序一个杂乱无章的数组怎么办呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 5][]

很明显。以上排序不正确。所以就应该先把left和right数组排好序后再进行整体的排序。（这个地方写错了应该是1 2 7 5 4 8 9 6 3 10）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 6][]

右边的right依然是未排好序的，所以继续对right进行划分排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 7][]

这样就对右边排好序了，然后就可以进行对原数组a的left进行排序了。所以这是一个递归的过程。

就是一直把数组从中间分开，把两边进行排序，就是一个递归的的过程。

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 = [4, 7, 8, 3, 5, 9]
        print(merge_sort(a))

[20190327215212768.png]: /images/20210508/ecc7ea09ef784975855c2adbccefbeec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70]: /images/20210508/b66aec6daa284e79a0e4c6454b752458.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 1]: /images/20210508/5c8ea4fb87dc49bc84c94f553b31688d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 2]: /images/20210508/2cbae1616eaf446bb42c4e2de4d214fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 3]: /images/20210508/9348887d7a8b4e47a5efc603aa8882f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 4]: /images/20210508/df0712b0ec9f49f4b05fb438d741806f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 5]: /images/20210508/786e0ac7639d4e8daf66cc97dd8650b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 6]: /images/20210508/3e4672a5ef224bbc9df572f291941ae2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjgzMTk1_size_16_color_FFFFFF_t_70 7]: /images/20210508/026a19d8f6ec4fb0ac5cf1cad0cd1c71.png