快速排序作为分治代表，通常实现由三步
- 数据中选择一个元素作为”基准”（pivot），通常选取最后一个元素；
- 分区(partition) 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
实现过程中有两种算法可以参考，一种是需要额外空间，另外一种就是经典的原地排序，第一种效率比较低，比较容易看懂；
辅助空间
func quickSort(data:[Int])->[Int]{
if data.count<=1 {
return data
}
var left:[Int] = []
var right:[Int] = []
let pivot:Int = data[data.count-1]
for index in 0..<data.count-1 {
if data[index] < pivot {
left.append(data[index])
}else{
right.append(data[index])
}
}
var result = quickSort(data: left)
result.append(pivot)
let rightResult = quickSort(data: right)
result.append(contentsOf: rightResult)
return result
}
经典快排
func partition( data:inout [Int],low:Int,high:Int) -> Int {
let root = data[high]
var index = low
for i in low...high {
if data[i] < root {
if i != index {
swap(&data[i], &data[index])
}
index = index+1
}
}
if high != index {
swap(&data[high], &data[index])
}
return index
}
func quickSort(data:inout [Int],low:Int,high:Int) -> Void {
if low > high {
return
}
let sortIndex = partition(data: &data, low: low, high: high)
quickSort(data: &data, low: low, high: sortIndex-1)
quickSort(data: &data, low: sortIndex+1, high: high)
}
测试代码:
let data:[Int] = [1,2,3,2,4,8,9,10,19,0]
let result = quickSort(data: data)
print("FlyElephant方案1:-\(result)")
var arr:[Int] = [10,3,17,8,5,2,1,9,5,4]
quickSort(data: &arr, low: 0, high: arr.count-1)
print("FlyElephant方案2:-\(arr)")
FlyElephant.png
