總所周知 快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用。
基本原理是:
數(shù)組a = [1,3,5,7,6,4,2]
1 選定一個(gè) 基準(zhǔn) a[0]
2 把比 a[0]小的放左邊，比a[0]大的放右邊. 中斷遞歸如果少于兩個(gè)數(shù)字 則不執(zhí)行。
3 然后再分別對(duì)兩邊 執(zhí)行 1，2，3操作。
對(duì)快速排序 的 想法
1 在待排序元素 大部分是有序的情況下， 速度 非常很快。
2 在最差的情況下，速度就很慢了。 相當(dāng)于冒泡了
3 所以 快排的 優(yōu)化， 定基準(zhǔn) 非常重要，例如待排序是有序的，基準(zhǔn)定在中間，xiao'lv
4 時(shí)間復(fù)雜度為nlogn，不穩(wěn)定排序
輔助空間
func quickSort(data:[NSInteger])->[NSInteger]{ if data.count<=1 { return data } var left:[NSInteger]=[] var right:[NSInteger]=[] let pivot:NSInteger=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(left) result.append(pivot) let rightResult=quickSort(right) result.appendContentsOf(rightResult) return result}經(jīng)典快排
func partition(inout data:[NSInteger],low:NSInteger,high:NSInteger) -> NSInteger { 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(inout data:[NSInteger],low:NSInteger,high:NSInteger) -> Void { if low>high { return } let sortIndex = partition(&data, low: low, high: high) quickSort(&data, low: low, high: sortIndex-1) quickSort(&data, low: sortIndex+1, high: high)}測(cè)試代碼:
var data:[NSInteger] = [1,2,3,2,4,8,9,10,19,0]var result=quickSort(data)print("FlyElephant方案1:-/(result)")var arr:[NSInteger] = [10,3,17,8,5,2,1,9,5,4]quickSort(&arr, low: 0, high: arr.count-1)print("FlyElephant方案2:-/(arr)") 
極簡(jiǎn)版本
import UIKit extension Array { var decompose : (head: Element, tail: [Element])? { return (count > 0) ? (self[0], Array(self[1..<count])) : nil } } func qsortDemo(input: [Int]) -> [Int] { if let (pivot, rest) = input.decompose { let lesser = rest.filter { $0 < pivot }//這里是小于于pivot基數(shù)的分成一個(gè)數(shù)組 let greater = rest.filter { $0 >= pivot }//這里是大于等于pivot基數(shù)的分成一個(gè)數(shù)組 return qsortDemo(lesser) + [pivot] + qsortDemo(greater)//遞歸 拼接數(shù)組 } else { return [] } } var a:[Int] = [1,2,4,6,2,4,3,7,8] qsortDemo(a)新聞熱點(diǎn)
疑難解答
圖片精選
