一文看懂归并排序 python实现-蒲公英云

一文看懂归并排序 python实现

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

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

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

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))