對于經(jīng)典算法挪蹭，你是否也遇到這樣的情形：學時覺得很清楚，可過陣子就忘了休偶？
本系列文章就嘗試解決這個問題梁厉。
研讀那些排序算法，細品它們的名字踏兜，其實都很貼切词顾。
比如快速排序八秃，一個快字就能體現(xiàn)出其價值，因而它是用得最多的肉盹。
因為它相對難一些昔驱，本系列將分兩篇文章講解它。
快速排序這個名字是針對其性能來起的垮媒，但很難讓人做到見名知意舍悯。
所以，給它重新起了個名字：歸分排序睡雇。
與歸并算法一樣萌衬，歸分算法也是分而治之算法，講究分它抱、歸秕豫、并。歸并的重頭戲在于如何去合并观蓄，快排的重頭戲在于如何去劃分混移。
上圖中，先把數(shù)組按最后一個元素4作為分界點侮穿，把數(shù)組一分為三歌径。除了分界點之外怜森，左子部分全是小于等于4的郭膛，右子部分全是大于4的，它們可以進一步遞歸排序跋炕。因為是原地排序（不需要額外空間）克锣，因此不需歸并那種合并操作茵肃。
其中，歸相對容易些袭祟，該算法的核心是：如何把數(shù)組按分界點一分為三验残？
各個教程的實現(xiàn)方式不一，這里我介紹一個最容易理解的方式巾乳。
具體過程是這樣的您没，選取最后一個元素為分界點，然后遍歷數(shù)組找小于等于分界點的元素胆绊，然后往數(shù)組前面交換氨鹏。比如：
上圖中，我們按順序找小于等于4的元素辑舷，共1、2槽片、3何缓、4肢础。然后分別與數(shù)組的前4個元素交換即可，結(jié)果自然是一分為三碌廓。
是不是非常容易理解的思路传轰？快排也不難學嘛。
我們用JS實現(xiàn)一遍：
let array = [7, 1, 6, 5, 3, 2, 4]
let j = 0
let pivot = array[array.length - 1]
for (let i = 0; i < array.length; i++) {
if (array[i] <= pivot) {
swap(array, i, j++)
}
}
console.log(array) // [ 1, 3, 2, 4, 7, 6, 5 ]
其中swap函數(shù)封裝了兩個元素如何交換：
function swap(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
進一步封裝成函數(shù)：
function partition(array, start, end) {
let j = start
let pivot = array[end]
for (let i = start; i <= end; i++) {
if (array[i] <= pivot) {
swap(array, i, j++)
}
}
return j - 1
}
start和end表示數(shù)組起止下標谷婆。最后返回的j-1是分界點的位置慨蛙。
接下來就需要遞歸處理左子部分和右子部分了。
對于遞歸纪挎，雖然它不符合線性思維期贫，但其實也沒啥難的。
只要有遞歸步驟（遞歸公式）异袄，很容翻譯成代碼的通砍。
我們再回憶一下快排算法的步驟：
- 數(shù)組分成三部分left、pivot烤蜕、right封孙，使left<=pivot，right>pivot讽营。
- 遞歸處理left
- 遞歸處理right
輕松翻譯成代碼：
function quickSort(array, start = 0, end = array.length -1) {
let pivotIndex = partition(array, start, end)
quickSort(array, start, pivotIndex - 1)
quickSort(array, pivotIndex + 1, end)
return array
}
遞歸是自身調(diào)用自身虎忌，不能無限次的調(diào)用下去，因此需要有遞歸出口（初始條件）橱鹏。
它的遞歸出口是膜蠢，當數(shù)組元素個數(shù)為小于2時，就是已經(jīng)是排好序的蚀瘸，不需要再遞歸調(diào)用了狡蝶。
因此需要在前面加入代碼：
if (end - start < 1) return array
至此，快速排序原理和實現(xiàn)已經(jīng)說完了贮勃。
快排的算法主要在于partition函數(shù)的實現(xiàn)贪惹，不同教程的實現(xiàn)方式都不一樣，這個需要注意一下寂嘉。
其時間復雜度平均是O(nlogn)奏瞬。最壞情形是，假如待排的數(shù)組已經(jīng)是排好序的泉孩，該算法將退化成O(n^2)級的硼端。此時可以通過合理的分區(qū)點選擇來避免。常見策略有選中間寓搬、隨機選珍昨、三選一等。假如這里我們隨機選一個分區(qū)點，再與最后的元素交換镣典，就能大概率避免最壞情形的出現(xiàn)兔毙。完整代碼：
const utils = {
swap(array, a, b) {
[array[a], array[b]] = [array[b], array[a]]
},
randomNum() {
return Math.floor(Math.random() * 100)
},
randomArray() {
return Array.from(Array(this.randomNum()), _ => this.randomNum())
}
}
function partition(array, start, end) {
let j = start
let pivot = array[end]
for (let i = start; i <= end; i++) {
if (array[i] <= pivot) {
utils.swap(array, i, j++)
}
}
return j - 1
}
function quickSort(array, start = 0, end = array.length -1) {
if (end - start < 1) return array
let pivotIndex = partition(array, start, end)
quickSort(array, start, pivotIndex - 1)
quickSort(array, pivotIndex + 1, end)
return array
}
let array = utils.randomArray()
console.log(quickSort(array))
這里總結(jié)一下，快速排序是原地算法兄春，不需要額外空間澎剥，但遞歸是需要空間的的（相當于手動維護個調(diào)用棧），總體空間復雜度是O(logn)赶舆。相等元素可能會交換前后順序哑姚，因而不是穩(wěn)定排序（因為交換）。時間復雜度為O(nlogn)芜茵。
快速排序叙量，要做到能分分鐘手寫出來，是需要掌握其排序原理的夕晓。關(guān)鍵在于宛乃，如何按照分界點把數(shù)組一分為三。至于遞歸蒸辆，只要能說清楚遞歸步驟和出口征炼，就能很容易寫出來，不需要死記硬背的躬贡。
希望有所幫助谆奥，本文完。
