快速排序作為分治代表棉胀，通常實現(xiàn)由三步
- 數(shù)據(jù)中選擇一個元素作為”基準”（pivot），通常選取最后一個元素霎挟；
- 分區(qū)(partition) 所有小于”基準”的元素麻掸，都移到”基準”的左邊脊奋；所有大于”基準”的元素蒜埋，都移到”基準”的右邊整份。分區(qū)操作結(jié)束后讲冠，基準元素所處的位置就是最終排序后它的位置竿开。
- 對”基準”左邊和右邊的兩個子集否彩，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。
實現(xiàn)過程中有兩種算法可以參考砂吞，一種是需要額外空間崎溃，另外一種就是經(jīng)典的原地排序，第一種效率比較低袭蝗，比較容易看懂般婆；
輔助空間
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
}
經(jīng)典快排
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
