快速排序：顧名思義就是快貌夕，c語言底層實現(xiàn)的排序算法主要就是用的快速排序律歼。
快速排序，最好時間復(fù)雜度是nlogn,最壞是n^2,一般時間復(fù)雜度是nlogn啡专。
func quickSort(_ array: inout Array<Int>, _ left: Int, _ right: Int) -> Void{
if left < right {
let point = partition(&array, left, right)
quickSort(&array, left, point - 1)
quickSort(&array , point + 1, right)
}
}
func partition(_ array: inout Array<Int>, _ left: Int, _ right: Int) -> Int {
let pivot = array[right] // 選最后一個數(shù)作為基準(zhǔn)值
var i = left // 暫時初始化想選的中間值為最左值险毁，動態(tài)改變更適合的中間值位置
for j in left ..< right { // 從最左邊遍歷數(shù)組，除了最后一個已經(jīng)挑出來的數(shù)
if array[j] < pivot {// 把遍歷得到的數(shù)和最后一個數(shù)進行比較，如果它比最后數(shù)小畔况，則說明需要它和暫時選擇的中間值進行交換离唐，
array.swapAt(j, i)
i += 1// 這里加1，是需要理解i值的作用问窃，它是暫時的中間值下標(biāo)，也就是說它應(yīng)該起到分割數(shù)據(jù)的作用完沪，左邊的數(shù)都是小于基準(zhǔn)值的域庇，右邊是待比較的數(shù)據(jù)，通過上面一步的交換后覆积，說明舊的i下標(biāo)現(xiàn)在存儲的值是小于基準(zhǔn)值的听皿，如果不加1，那就起不到分割數(shù)據(jù)的作用宽档，所以加1后尉姨，相對于新i下標(biāo)，左邊的數(shù)又是小于基準(zhǔn)值的吗冤。
}
}
array.swapAt(right, i)
return i
}
原地分區(qū)函數(shù) 不占有額外空間又厉，空間復(fù)雜度為O(1)，經(jīng)過最后處理后椎瘟，得到的是中間值的和中間值位置覆致，而它的左邊的數(shù)肯定都是比它小的數(shù)，當(dāng)然也要知道左邊的數(shù)不一定是排好序的肺蔚，而它的右邊肯定都是比它大或者等于的數(shù)煌妈，右邊的數(shù)也不一定都排好序。舉個例子好理解宣羊。
待排序數(shù)據(jù)是：3 4 2 1 5 3 璧诵。
跑完一次分區(qū)函數(shù)結(jié)果為 2 1 3 4 5 3。
其中i值仇冯，此時是2之宿，是下標(biāo) ,而對應(yīng)的值是3。
遍歷第1輪（i , j = 0）： 3[a] (i,j） 4 2 1 5 3(b) 由于3[a]和3(b)一樣赞枕，所以不交換澈缺，
遍歷第2輪（i = 0 , j = 1）: 3[a] (i） 4(j) 2 1 5 3(b) 由于4大于3(b)，所以不交換
遍歷第3輪（i = 0 , j = 2）: 3[a] (i） 4 2(j) 1 5 3(b) 由于2小于3(b)炕婶，所以交換i ,j 值姐赡，同時i + 1
遍歷第4輪（i = 0 , j = 3）: 2 4(i） 3[a] 1(j) 5 3(b) 由于1小于3(b)，所以交換i ,j 值柠掂，同時i + 1
遍歷第5輪（i = 0 , j = 4）: 2 1 3[a](i) 4 5(j) 3(b) 由于5大于3(b)项滑，所以不交換
遍歷結(jié)束，最后把最后沒有參與比較的基準(zhǔn)數(shù)和最后取得的i下標(biāo)的值進行交換涯贞，因為此時i值就是給基準(zhǔn)數(shù)的枪狂，相當(dāng)于經(jīng)過交換才真正歸位到正確的位置i
從上面對于相同數(shù)據(jù)3的排序危喉，沒跑函數(shù)前相對位置是3[a] 3[b],而跑完函數(shù)就變成了 3[b] 3[a],說明快速排序不是穩(wěn)定的排序。
結(jié)論：參考穩(wěn)定算法的定義州疾，如果相同的數(shù)辜限，排序前后發(fā)生了交換，那就不是穩(wěn)定的排序算法严蓖，而從上面的分析就可以知道快速排序是不穩(wěn)定的薄嫡。
還有可以發(fā)現(xiàn)快速排序的分區(qū)函數(shù)并沒有使用到臨時數(shù)組，所以它的分區(qū)函數(shù)空間復(fù)雜度是O(1)颗胡，但由于快速函數(shù)外面是通過遞歸調(diào)用的毫深，所以還需要用到遞歸棧空間毒姨，所以經(jīng)過復(fù)雜的計算得到平均整體時間復(fù)雜度為O(logn),最壞是O(logn)哑蔫，最好是O(logn)。
快速排序常見的排序題：
查找無序數(shù)組中弧呐，第k大的數(shù)闸迷，也就是對應(yīng)的下標(biāo)應(yīng)該是k-1
func quickSortSelectK(_ array: inout Array<Int>, _ left: Int, _ right: Int, _ k: Int) -> Int {
if left == right {
return array[left]
}
let point = partition(&array, left, right) // 求得的是中間值的下標(biāo)
let realIndex = k - 1 // 實際要求的下標(biāo)
if point == realIndex {
return array[point]
}else if (point > realIndex) {// point的下標(biāo)比realIndex大，說明真正要找的數(shù)在point的左邊俘枫，需要再對左邊區(qū)間數(shù)據(jù)做一次快速排序
return quickSortSelectK(&array, left, point - 1, k) // 注意不包括point
}else {// point的下標(biāo)比realIndex小稿黍，說明真正要找的數(shù)在point的右邊，所以需要再對右邊區(qū)間數(shù)據(jù)做一次快速排序
return quickSortSelectK(&array, point + 1, right, k)// 注意不包括point
}
}
