1738: 排序 -python归并排序

注意事项: 注意输入输出

参考代码:

# 归并排序_升序
def merge_sort(nums):
    # 待排序数组只有一个元素 => 无需排序 返回
    if len(nums) <= 1:
        return nums
    # 分
    mid = len(nums) // 2  # 中间索引
    left_nums = nums[: mid]  # 左边元素
    right_nums = nums[mid:]  # 右边元素
    # 递归对左右元素进行归并排序
    merge_sort(left_nums)
    merge_sort(right_nums)
    # 合并两个有序数组
    # i => 左边元素的指针 j => 右边元素的指针
    # k => 在原数组上操作的指针
    i = j = k = 0
    while i < len(left_nums) and j < len(right_nums):
        # 右边的更小
        if left_nums[i] > right_nums[j]:
            # 插入数组
            nums[k] = right_nums[j]
            # 往后移
            j += 1
        # 右边的更小
        else:
            # 插入数组
            nums[k] = left_nums[i]
            # 往后移
            i += 1
        k += 1
    # 下面情况是 两个数组其中一个已经比较完毕 所以要将另一个数组全部插入nums
    while i < len(left_nums):
        nums[k] = left_nums[i]
        i += 1
        k += 1
    while j < len(right_nums):
        nums[k] = right_nums[j]
        j += 1
        k += 1
    return nums


while True:
    try:
        n = eval(input())
        lists = list(map(eval, input().split()))
        lists = merge_sort(lists)
        for index in range(n):
            if index != n - 1:
                print(lists[index], end=" ")
            else:
                print(lists[index])
    except Exception:
        break