上一篇文章我们讲到了解决宝藏排序的三种基本排序方法，这篇文章我们深入探讨一下两种进阶排序：快速排序和归并排序。让我们拿起键盘，一起敲起来吧！
宝藏排序题目：
快速排序详解：
解题思路：
找一个基准值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】作为一个子问题求解
代码演示：
代码语言：javascript复制# 列表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、将两个有序列表合并起来
代码演示：
代码语言：javascript复制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
"""
