数据结构和算法-排序算法-归并排序

"""
归并算法逻辑

拆分
对整个序列进行拆分，左边一部分，右边一部分
然后对每一部分再次进行拆分，一直到拆分到只有一个元素，就到头了，
第1次拆分：54, 26, 93, 17, 77, 31, 44, 55,
第2次拆分：54, 26, 93, 17,      77, 31, 44, 55,
第3次拆分：54, 26,        93, 17,       77, 31,      44, 55,
第4次拆分：54,     26,        93,   17,       77,   31,      44,   55,

合并
然后把拆分到的再次合并，小的在前，大的在后，
第1次合并：26,54,     17,93       31,77,      44, 55,
第2次合并，需要借助两个游标，left，right，
26,54,     17,93
左边游标初始指向26，右边游标初始指向17，
然后左边第一个的和右边的依次比较，如果左边小，数字不动，然后右边的游标往后移动，如果右边小，就把左右的数字交换，
然后比较完左边的第一个，然后就是第二个，知道把数字都从小到大排序，
第3次合并的方式都是一样的，直到所有的都排序完毕，

代码实现，
还是需要使用到递归，

"""

def merge_sort(alist):
    n=len(alist)
    if n <=1 :  # 这是如果只有一个元素不往下拆分了，这也是递归结束的条件
        return alist
    mid = n//2
    # 这是左边的部分
    left = merge_sort(alist[:mid])
    # 这是右边的部分，
    right =merge_sort(alist[mid:])
    # 合并：
    # merge(left,right)

    # 定义两个游标
    left_pointer ,right_pointer=0,0
    result=[]

    while left_pointer<len(left) and  right_pointer < len(right):
        if left[left_pointer]<right[right_pointer]:
            result.append(left[left_pointer])
            left_pointer+=1
        else:
            result.append(right[right_pointer])
            right_pointer+=1
    result +=left[left_pointer:]
    result += right[right_pointer:]
    return result


if __name__ == ‘__main__‘:
    alist = [54,26,93,17,77,31,44,55,20]
    print(alist)
    sorted_alist = merge_sort(alist)
    print(sorted_alist)

# 这样排序就结束了，下面讲搜索，