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

 ##################     归并排序        #######################

"""
归并算法逻辑

拆分
对整个序列进行拆分,左边一部分,右边一部分
然后对每一部分再次进行拆分,一直到拆分到只有一个元素,就到头了,
第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)# 这样排序就结束了,下面讲搜索,