《啊哈厌蔽！算法》第 1 章第 3 節(jié)畦贸，快速排序的 Swift 實(shí)現(xiàn)
問題
為給定數(shù)字序列排序
解決
以左側(cè)第一個(gè)位置為基準(zhǔn)數(shù)告希，假設(shè)最左側(cè)索引值為 i桥温，最右側(cè)索引值為 j引矩，先從右往左找小于基準(zhǔn)數(shù)的值，然后左側(cè)往右找大于基準(zhǔn)數(shù)的值侵浸，找到后交換位置旺韭，直到 i 與 j 相遇，此時(shí)將最左側(cè)基準(zhǔn)數(shù)與索引 i 位置的值交換位置掏觉，接著遞歸循環(huán)為左右兩側(cè)分別排序区端。
var array = [3, 1, 2, 5, 4, 6, 9, 7, 10, 8]
func quicksort( left: Int, right: Int){
var i: Int, j: Int, temp: Int
if left > right {
return
}
temp = array[left] //temp 存基準(zhǔn)數(shù)
i = left
j = right
//兩邊向中間查找，與基準(zhǔn)數(shù)相比較履腋，直到i和j相遇
while i != j {
//先從右往左找小于基準(zhǔn)數(shù)的數(shù)
while array[j] >= temp && i < j {
j -= 1
}
//再?gòu)淖笸艺掖笥诨鶞?zhǔn)數(shù)的數(shù)
while array[i] <= temp && i < j {
i += 1
}
//找到后如果沒有相遇珊燎，那么交換位置
if i < j {
swap(&array[i], &array[j])
}
}
//當(dāng) i 和 j 相遇時(shí)，將基準(zhǔn)數(shù)與當(dāng)前位置的值交換位置遵湖，基準(zhǔn)數(shù)歸位
array[left] = array[i]
array[i] = temp
//接著用同樣的方法給基準(zhǔn)數(shù)左邊與右邊兩個(gè)序列分別排序
quicksort(left: left, right: i-1) //繼續(xù)處理左邊，遞歸過程
quicksort(left: i+1, right: right) //繼續(xù)處理右邊晚吞，遞歸過程
}
quicksort(left: 0, right: array.count-1)
for item in array {
print("\(item)")
}
快速排序的最差時(shí)間復(fù)雜度和冒泡排序一樣為O(N2)延旧，平均時(shí)間復(fù)雜度為O(NLogN)。
代碼在 GitHub
