Python 排序算法之归并排序(7/8)

2018-05-17  本文已影响41人  Paycation

思想

将列表进行递归的对半拆分,直到只剩下一个元素。然后,进行合并。
合并的方式可以这样理解:
左右两根管子里面装着数字球(经过排序)。首先比较那个球的数字大,大的一方就倒入一个叫 result 的竖管里。然后后面的数字球补空位。
当某一个管子为空时,另一方全部倒入 result。合并完成。


灵魂画师

注意管子里的数本身要经过排序。如何确保这一点?那就是不停拆分,直到每个小列表只剩一个元素,那么两两合并就可以保证合并的结果是有序的。然后重复此过程,直到所有元素都合并,排序完成。

代码实现

def merge(left, right):
    result = []
    while len(left)>0 and len(right)>0 :
        if left[0] <= right[0]: # 倒数字球的过程
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    # 剩余的一并倒入
    result += left
    result += right
    return result

def merge_sort( li ):
    # 拆分到只剩一个元素为止
    if len(li) == 1:
        return li
    mid = len(li) // 2
    left = li[:mid]
    right = li[mid:]

    ll = merge_sort( left )
    rl =merge_sort( right )
    return merge(ll , rl)

带着实际的参数我们来走一遍:
[2, 1]
那么 merge_sort 第一次,分成 2 组 (2//2=1):
[2] 和 [1]
然后递归,再 merge_sort 一次,变成:
左右分别返回 [2], [1] 本身。也就是:
ll = [2]
rl = [1]
然后运行 merge(ll, rl),把大的吐出来,最后就是结果了。

上一篇下一篇

猜你喜欢

热点阅读