python自学python小课——零基础入门——学习笔记

python实现归并排序 -- 详细思路分析

2020-07-01  本文已影响0人  于饼喵

1. 归并排序思想

是建立在归并操作上的一种有效的排序算法。先将数组分解成多个元素,然后对分解后的元素进行排序和合并。

2. 快速排序实现步骤

假设有一个列表[9,7,3,3,6,2,1,4,10],需要使用快速排序,将其排序为有序列表。、

2.1 分解过程


分解过程图
def merge_sort(target_list):
    """拆分过程"""
    n = len(target_list)
    # 中间元素位置的索引
    mid = n // 2 
    if n <=1 :
        return alist
    # 使用递归进行拆分
    # left_ist 和 right_list 代表采用归并排序后形成的新的列表
    left_list = merge_sort(target_list[:mid])
    right_list = merge_sort(target_list[mid:])

2.2 排序和合并过程

排序和合并图解
def merge_sort(target_list):
    
    n = len(target_list)
    # 当n的长度小于1时停止拆分【递归终止条件】
    if n <= 1:
        return target_list
    mid = n // 2
    
    # 使用递归,将列表拆分
    # 使用left_list 和 right_list接受拆分并排序后的result
    left_list = merge_sort(target_list[:mid])
    right_list = merge_sort(target_list[mid:])
    
    # 排序 + 合并过程
    # 创建左、右游标,并置于首位
    left_cursor = 0
    right_cursor = 0
    # 新列表,用于接受排序后的元素
    result = []
    while left_cursor < len(left_list) and right_cursor < len(right_list):
        if left_list[left_cursor] <= right_list[right_cursor]:
            result.append(left_list[left_cursor])
            left_cursor += 1
        else:
            result.append(right_list[right_cursor])
            right_cursor += 1
    
    # 当左边或右边的列表内没有元素时,result添加剩下列表内的元素
    result += left_list[left_cursor:]
    result += right_list[right_cursor:]
    
    return result
上一篇 下一篇

猜你喜欢

热点阅读