python学习笔记_第 32天(归并排序)

归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组
将数组分解最小之后,依次合并两个有序数组。基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位;然后再比较,直至一个数组为空,最后把另一个数组的剩余部分追加。

归并排序的分析

快速排序传入本身列表,通过控制操作范围达成排序目的
归并排序则传入原序列切片后生成的新的子序列

def merge_sort(alist):
    '''归并排序'''
    '''对列表进行拆分'''
    n = len(alist)
    # 1.先将列表进行拆分,直至拆分到每个分组只有一个元素
    if n <= 1:  # 递归终止条件
        return alist  # 当序列只有一个值时无需排序,直接返回序列本身
    else:
        mid = n // 2
        # 此时将列表分成两个部分
        left_li = merge_sort(alist[mid:])  # 对拆分后的部分再调用归并排序,返回left_li和right_li是有序的新列表
        right_li = merge_sort(alist[:mid])
        '''对列表进行合并'''
        left_pointer, right_pointer = 0, 0
        # 2.将两个有序的子序列,合并成一个新的整体
        result = []  # 子序列合并后为一新列表,建一个空列表用于存储
        while left_pointer < len(left_li) and right_pointer < len(right_li):
            if left_li[left_pointer] <= right_li[right_pointer]:
                result.append(left_li[left_pointer])
                left_pointer += 1
            else:
                result.append(right_li[right_pointer])
                right_pointer += 1
        # 当退出循环体时,左右两个部分至少有一个指针已遍历完,则在整体后追加另一边游标未处理的剩余数据
        result.extend(left_li[left_pointer:])  # 列表.extend(列表),直接在原对象上追加新列表,不生成新对象占用空间
        result.extend(right_li[right_pointer:])  # 对一个列表,当超出列表长度进行切片,则返回一个空列表,不报错
        return result  # 返回新对象result

测试

if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55]
    print(li)
    sorted_li = merge_sort(li)  # 归并排序的返回值为一个已排序的新列表,不对原列表本身排序
    print(li)
    print(sorted_li)

执行结果:
[54, 26, 93, 17, 77, 31, 44, 55]
[54, 26, 93, 17, 77, 31, 44, 55]
[17, 26, 31, 44, 54, 55, 77, 93]

归并函数代码执行顺序

缩进代表在一个递归函数内

1.merge_sort([54, 26, 93, 17, 77, 31, 44, 55])
# 运行到left_li = merge_sort(alist[mid:])
    2.left1_li = merge_sort([54, 26, 93, 17])  # 递归函数,打开下层函数搁置一边
        3.left2_li = merge_sort([54, 26])
            4.left3_li = merge_sort([54])  # 再调用函数时,得到第一个返回值[54]
            # 回到上一步搁置代码处,继续执行该循环体中的下行代码:right_li = merge_sort(alist[:mid])right2_li = merge_sort([54,26][1:])
            5.right3_li = merge_sort([26])  # 返回值[26],关闭最里层递归函数
        6.result = [26, 54] # 此时merge_sort([54, 26])继续执行向下执行result循环体部分,进行合并
        7.right2_li = merge_sort([93, 17])
            8.left3_li = merge_sort([93])
            9.right3_li = merge_sort([17])
        10.result = [17, 93]
    11.result = [17, 26, 54, 93]
    12.right_li = merge_sort([77, 31, 44, 55])
        13.left2_li = merge_sort([77, 31])
            14.left3_li = merge_sort([77]) 
            15.right3_li = merge_sort([31]) 
        16.result = [31, 77]
        17.right2_li = merge_sort([44, 55])
            18.left3_li = merge_sort([44])
            19.right3_li = merge_sort([55])
        20.result = [44, 55]
    21.result = [31, 44, 55, 77]
22.result = [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

归并排序代码,对序列的拆分是顺序结构时间复杂度为O(1)。进入合并部分代码后为循环体层级数与层级做乘法运算;每一层级级合并都是顺序执行的,对应的时间复杂度做加运算。每一级数据的合并都要经过两两之间条件对比,时间复杂度为O(n);合并的层级次数2^x=n,即x=log2(n),时间复杂度O(logn)。
与快速排序不同对归并排序,永远从中轴线开始拆分,不存在分割线严重偏离的情况,所以最坏时间复杂度还是O(nlogn)。
通过条件if left_li[left_pointer] <= right_li[right_pointer],考虑等号可以确保排序的稳定性。
整体时间复杂度O(nlogn)

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性:稳定

归并排序是冒泡、选择、插入、希尔、快速这些排序中最坏时间复杂度最小的,最坏时间复杂度为O(nlogn)。但归并排序返回的是一个排序后的新列表,占用了两份列表空间(原无序列表+新有序列表)。

常见排序算法效率比较

至少会写3种排序算法,快速排序常用必需会!
快速排序平均时间复杂度为O(nlogn),且不需要额外的存储空间。
python学习笔记_第 32天(归并排序)

上一篇:54 Spring Cloud Sleuth与ELK(日志分析系统)配合使用


下一篇:剑指 Offer 29. 顺时针打印矩阵 && Leetcode 54. 螺旋矩阵