上一篇文章我们讲到了解决宝藏排序的三种基本排序方法，这篇文章我们深入探讨一下两种进阶排序：快速排序和归并排序。让我们拿起键盘，一起敲起来吧！
宝藏排序题目：
快速排序详解：
解题思路：
找一个基准值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:
