python实现归并排序

末蓝、 2022-11-02 11:55 193阅读 0赞

**归并排序**  
“归并"是将两个或者两个以上的有序表组成一个新的有序表。假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为一，然后两两归并，得到n//2个长度为2或1的有序表；再两两归并，…直到合并成一个长度为n的有序表为止，这种方法称为2-路归并排序。  
![在这里插入图片描述][20210225125407133.png]  
归并算法动态实现：  
![在这里插入图片描述][2021032413100384.gif_pic_center]  
实现代码如下：

#merge的功能是将前后相邻的两个有序表归并为一个有序表的算法。
    def merge(left, right):
        ll, rr = 0, 0
        result = []
        while ll < len(left) and rr < len(right):
            if left[ll] < right[rr]:
                result.append(left[ll])
                ll += 1
            else:
                result.append(right[rr])
                rr += 1
        result+=left[ll:]
        result+=right[rr:]
        return result
    
    def merge_sort(alist):
        if len(alist) <= 1:
            return alist
        num = len(alist) // 2   # 从中间划分两个子序列
        left = merge_sort(alist[:num]) # 对左侧子序列进行递归排序
        right = merge_sort(alist[num:]) # 对右侧子序列进行递归排序
        return merge(left, right) #归并
    
    tesl=[1,3,45,23,23,12,43,45,33,21]
    print(merge_sort(tesl))
    #[1, 3, 12, 21, 23, 23, 33, 43, 45, 45]

空间效率：需要n个辅助空间,因此空间复杂度为O(n)  
时间效率：归并时间复杂度为O(n),一共进行log2 N趟，因此时间复杂度为O(nlog2 N)  
它是一种稳定的排序算法。

[20210225125407133.png]: /images/20221024/d16d00d05d0a4bd9b5348548c458b759.png
[2021032413100384.gif_pic_center]: /images/20221024/0e6f7e2b6e7f4636a662b1817d0008d2.png