归并排序

归并排序

归并排序的思想源于分而治之,即不断地把数组进行拆分,一直拆分成直到还有一个元素,然后再两两合并,所以需要一个帮助函数,这个帮助函数即对两个有序的数组进行排序


def merge(left, right):
    """
        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

上面的代码里面,也可以用index来做,不用pop

然后是归并排序的主体代码

def merge_sort(lst):
    """
        lst 是个列表
    """
    # 当分割到长度只有一个元素的时候就直接返回
    if len(lst) == 1:
        return lst

    # 找到拆分的中间位,进行分割 
    mid = len(lst)//2
    
    # 两个子列
    left = lst[:mid]
    right = lst[mid:]

    # 然后递归地对左右两个进行拆分
    left_lst = merge_sort(left)
    right_lst = merge_sort(right)
    
    # 然后调用上面的函数,将这两个排好序的数组排成一个数组并返回
    return merge(left_lst, right_lst)

测试过程

if __name__ == "__main__":
    li = list(range(20))[::-1]
    print(li)
    li2 = merge_sort(li)
    print(li2)

  • 结果
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]


打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦