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

1. 归并排序思想

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

2. 快速排序实现步骤

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

2.1 分解过程

---

• 找到数组中间位置mid mid = len(target_list) // 2
• 从数组中间位置不断拆分，直到将数组拆分为单个元素

分解过程图

• 代码实现

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 排序和合并过程

排序和合并图解

• 创建两个游标【图上的LEFT和RIGHT】，使用游标对各个部分的元素进行排序
  ○ LEFT游标放在左边列表的首位，RIGHT游标放在右边列表的首位
  ○ 对比当前两游标位置的元素，如果RIGHT游标所指向的数小，则将RIGHT游标所指向的元素排入新列表，然后RIGHT游标右移；如果LEFT右边所指向的数小，则将LEFT游标所指向的元素排入新列表，然后LEFT右移。
  ○ 直到左边列表或右边列表没有元素后，将剩余元素添加进新列表
  ○ 返回排序好的新列表
• 排序完成后合并，然后继续和其他数组进行排序和合并的过程
• 代码实现

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