快速排序作为分治代表，通常实现由三步
- 1.数据中选择一个元素作为”基准”（pivot），通常选取最后一个元素；
- 2.分区(partition) 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 3.对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止
解决方法一:需要额外空间辅助空间
func quickSort(data: [Int]) ->[Int]{
if data.count <= 1 {
return data
}
var left: [Int] = [Int]()
var right: [Int] = [Int]()
let pivot: Int = data.last!
for i in 0..<data.count-1 {
if data[i] < pivot{
left.append(data[i])
}else{
right.append(data[i])
}
}
print("left----------\(left)")
print("right----------\(right)")
// 递归左边小于pivot的数组
var result = quickSort(data: left)
print("result=\(result)")
result.append(pivot)
// 递归右边大于pivot的数组
let rightResult = quickSort(data: right)
print("rightResult=\(rightResult)")
result.append(contentsOf: rightResult)
return result
}
测试
let data:[Int] = [1,8,3,5]
let result = quickSort(data: data)
print(result)
打印
left----------[1, 3]
right----------[8]
left----------[1]
right----------[]
result=[1]
rightResult=[]
result=[1, 3]
rightResult=[8]
[1, 3, 5, 8]
