快速排序（Swift实现）
func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
//需要排序的区间只包含一个数字，则不需要重排数组，直接返回。
if low < high {
let pivot = partition(arr,low,high)
quickSort(arr,low,privot - 1)
quickSort(arr,privot + 1,high)
}
}
private partition(_ arr: inout [Int], _ low: Int, _ high: Int) {
var pivot = arr[low]
while low < high {
//high哨兵要找到一个小于pivot的数前停下来
while low < high && arr[high] >= pivot {
high -= 1
}
arr[low] = arr[high]
//low哨兵要找到一个大于pivot的数前停下来
while low < high && arr[low] <= pivot {
low += 1
}
arr[high] = arr[low]
}
//此时退出循环的条件是哨兵low和哨兵high相遇
//将基准数归位
arr[low] = pivot
return low
}
//时间复杂度：O(nlog2n),最坏O(N^2) 空间复杂度：O(nlog2n) 是不稳定算法