一、简介
快速排序使用分治法（Divide and conquer）策略把一个序列分为较小或者较大两个子序列，然后递归排序两个子序列，从到底排序的目的。具体步骤为：
1、从序列中挑选一个元素作为基准（pivot）
2、根据基准元素将序列进行分割，比基准元素大或者小的，放到基准元素前面，反之放到后面（相等的放到那边都可以）。
3、递归子序列，将子序列再次按照相同方法进行排序。
提示
递归时需要判断序列的大小是0或者1（此时序列显然是有序的），此时则停止递归！
二、实例
2.1 Go 实例
package examples
func QuickSort(arr []int, start, end int) {
// 判断是否需要排序
if end < start {
return
}
// 确定基准元素
pivot := arr[end]
// 用于记录边界位置（到时会把基准元素放到这里）
pi := start - 1
// 交换元素位置，将较大或者较小的元素放到基准元素的一侧
for i := start; i < end; i++ {
if arr[i] < pivot {
pi++
arr[pi], arr[i] = arr[i], arr[pi]
}
}
pi++
// 把基准元素放到边界上去
arr[pi], arr[end] = arr[end], arr[pi]
// 排序子序列（以边界元素）
QuickSort(arr, start, pi-1)
QuickSort(arr, pi+1, end)
}
2.2 Python 实例
def quick_sort(arr, start, end):
# 区间只有一个元素表示结束
if end < start:
return
# 用于记录边界
pi = start - 1
# 基准值
pivot = arr[end]
# 依次判断小于或者大于基准元素得值
# 条件成立就交换位置
# 使大于或者小于的元素都放在基准元素的一侧
for j in range(start, end):
print(j, end)
if arr[j] < pivot:
pi += 1
arr[pi], arr[j] = arr[j], arr[pi]
# 确定下一个区间的边界
pi += 1
# 将基准元素放到中间
arr[pi], arr[end] = arr[end], arr[pi]
# 再次排序前后分区
# pi ± 1，表示由基准元素划分的两个分区
quick_sort(arr, start, pi - 1)
quick_sort(arr, pi + 1, end)
arr = [10, 8, 2, 3, 7, 4, 9, 0, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)
