蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序

上一篇文章我们讲到了解决宝藏排序的三种基本排序方法，这篇文章我们深入探讨一下两种进阶排序：快速排序和归并排序。让我们拿起键盘，一起敲起来吧！

宝藏排序题目：

快速排序详解：

解题思路：

找一个基准值x

把列表分成三部分:小于等于x的数字，x，大于x的数字

左半部分和右半部分递归使用该策略

例: a=【3,5,8,1,2,9,4,7,6】

找到基准值3，【1,2】3 【5,8,9,4,7,6】

左半部分【1,2】作为一个子问题求解

右半部分【5,8,9,4,7,6】作为一个子问题求解

代码演示：

# 列表a，左端点为left，右端点为right
# [left, right]
def partition(a, left, right):
    """找一个基准值，然后把数组分成三部分"""
    # 基准值为a[left]
    idx = left + 1
    for i in range(left + 1, right + 1):
        # 如果元素小于基准值，放到前面去
        if a[i] <= a[left]:
            a[i], a[idx] = a[idx], a[i]
            idx += 1
    # 把前半部分最后一个和基准值交换
    a[left], a[idx - 1] = a[idx - 1], a[left]
    return idx - 1


# 对a[left, right]进行排序
def quicksort(a, left, right):
    if left < right:
        mid = partition(a, left, right)
        # 此时a分为三部分，(left,mid-1),(mid),(mid+1,left)
        quicksort(a, left, mid - 1)  # 递归，自己调用自己排序
        quicksort(a, mid + 1, right)


quicksort(a, 0, n - 1)
print(' '.join(map(str, a)))

?归并排序详解：

解题思路：

首先考虑一个问题:两个有序列表如何合并成一个列表：

A=【1,3,5,6,7】 、B=【2,3,4,9】

1、构建一个result=[]

2、当A非空且B非空:

? ? ? 比较A[0]和 B[0]

? ? ? result添加较小的那个元素，并从原始数组弹出

3、如果A非空，把A添加到result末尾

4、如果B非空，把B添加到result末尾

然后考虑归并排序的算法步骤：

1、先把数组分成两部分

2、每部分递归处理变成有序

3、将两个有序列表合并起来

代码演示：

def Merge(A, B):
    # 合并两个有序列表，返回出合并的结果
    result = []
    while len(A) != 0 and len(B) != 0:
        if A[0] <= B[0]:
            result.append(A.pop(0))
        else:
            result.append(B.pop(0))

    result.extend(A)
    result.extend(B)
    return result    # result为已排序好的合并后的序列

def MergeSort(A):
    if len(A) <= 2:
        return A
    mid = len(A) // 2
    # 分解成两部分，每部分递归处理
    left = MergeSort(A[:mid])
    right = MergeSort(A[mid:])
    return Merge(left, right)

n = int(input())
a = list(map(int, input().split()))
a = MergeSort(a)
print(' '.join(map(str, MergeSort(a))))
"""
输出格式参考：
7
3 2 1 4 5 6 7
"""