§01 排序算法
快速排序
分治策略的经典算法。选择一个基准元素（pivot），将数组分为小于和大于基准的两部分，递归排序。 平均时间复杂度 O(n log n)。
快速排序
伪代码
1
function quickSort(arr, low, high)
2
if low < high then
3
pi = partition(arr, low, high)
4
quickSort(arr, low, pi - 1)
5
quickSort(arr, pi + 1, high)
6
end if
7
end function
8
9
function partition(arr, low, high)
10
pivot = arr[high] // 选最右为基准
11
i = low - 1 // 小于区的右边界
12
13
for j = low to high - 1 do
14
if arr[j] <= pivot then
15
i = i + 1
16
swap arr[i] and arr[j]
17
end if
18
end for
19
20
swap arr[i+1] and arr[high] // pivot 放到正确位置
21
return i + 1
22
end function