Python之归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治法:

• 分割：递归地把当前序列平均分割成两半。
• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

程序在处理过程中打印每一步的处理结果，方便理解程序，可以尝试使用手动归并处理每一个步骤，然后和程序处理的结果进行比对，有助于加深理解

# 归并排序
import random,time


def merge_sort(arr):
    print('len(arr):',len(arr))
    if len(arr) <= 1:  # 当列表只有一个值时，直接返回列表
        return arr
    mid = len(arr) // 2  # 划分中间值（将列表划分成左右两个子列表）,// 取整除 - 往小的方向取整数
    print('mid=',mid)
    left = merge_sort(arr[:mid])  # 递归，持续调用函数自身并不断划分数据，调用至列表中只剩下一个元素--划分
    right = merge_sort(arr[mid:])  # 递归，持续调用函数自身并不断划分数据，调用至列表中只剩下一个元素--划分
    print('arr:',arr)  # 打印当前处理的arr
    print('left:',left)  # 打印当前的left列表
    print('right:',right)  # 打印当前的left列表
    print('------')  # 处理数据步骤分隔
    time.sleep(1)
    return merge(left, right)


def merge(left, right):  # 将左右列表作为参数传递给函数，完成归并
    result = []  # 创建空列表-用来存储排排好序的元素
    i = j = 0  # left,right设置变量及初始值
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # 如果左边的列表元素小于等于右边列表元素值
            result.append(left[i])  #将较小的值添加到result列表中
            i += 1  # i+1，迭代
        else:
            result.append(right[j]) # 将右边列表元素的值添加到result列表中
            j += 1  # j+1迭代
    result += left[i:]  # 向列表中添加剩余的元素
    result += right[j:]  # 向列表中添加剩余的元素
    print(result,'-----------merge')  # 打印处理好的列表
    return result  # 返回从小到大排列好的列表


numb_list = random.sample(range(1, 50), 9)  # 生成不重复的随机列表
print(numb_list, len(numb_list))  # 打印初始列表
print(merge_sort(numb_list))  # 打印归并排序的结果（及每一步的处理结果）