圖解算法基礎(chǔ)-快速排序，附 Go 代碼實(shí)現(xiàn)
很多面試題的解答都是以排序?yàn)榛A(chǔ)的，如果我們寫出一個(gè)
的算法，大概率要被掛，今天寫個(gè)快排的基礎(chǔ)文章，后面看情況再把歸并和堆排序?qū)懸粚?，至于選擇排序、冒泡排序這種時(shí)間復(fù)雜度高的就不寫了，有興趣的可以找書自己看一下。
文中算法的實(shí)現(xiàn)是用 Go 寫了一個(gè)比較簡(jiǎn)單的快速排序，方便大家理解(旁邊畫外音：其實(shí)是他好幾年沒面試了，太厲害的他也寫不出來)。
關(guān)于更優(yōu)秀的代碼實(shí)現(xiàn)，可以在評(píng)論區(qū)里發(fā)出來一起學(xué)習(xí)，相信咱們讀者里一定是臥虎藏龍，有不少算法大拿。
快速排序的思想
快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值(pivot)，然后將除了基準(zhǔn)值之外的數(shù)分為 "比基準(zhǔn)值小的數(shù)" 和 "比基準(zhǔn)值大的數(shù)" 這兩個(gè)類別，再將其排列成以下形式。
【比基準(zhǔn)值小的數(shù)】 基準(zhǔn)值 【比基準(zhǔn)值大的數(shù)】
接著，繼續(xù)對(duì)兩個(gè)序列 "【】"中的數(shù)據(jù)進(jìn)行排序之后，整體的排序便完成了。對(duì)基準(zhǔn)值左右兩側(cè)的序列排序時(shí)，同樣也會(huì)使用快速排序。
快速排序是一種"分治法"，將原本的問題分解成兩個(gè)子問題—— 比基準(zhǔn)值小的數(shù)和比基準(zhǔn)值大的數(shù)，然后再分別解決這兩個(gè)子問題。解決子問題的時(shí)候會(huì)再次使用快速排序，只有在子問題里只剩下一個(gè)數(shù)字的時(shí)候，排序才算完成。
快排的過程
下面我們用示意圖更好地理解一下快速排序?qū)σ粋€(gè)序列進(jìn)行排序的過程。
圖例出自—《我的第一本算法書》。
假定有如下待排序序列：
待排序序列
首先在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值，這里選擇了 4。
選擇基準(zhǔn)值 pivot
將其他數(shù)字和基準(zhǔn)值進(jìn)行比較，小于基準(zhǔn)值的往左移，大于基準(zhǔn)值的往右移。
首先比較第一個(gè)元素 3 和基準(zhǔn)值4，因?yàn)?3 < 4, 所以將 3放在基準(zhǔn)值的左邊。
首先比較 3 和基準(zhǔn)值4，因?yàn)?3 < 4, 所以將 3放在基準(zhǔn)值的左邊
接下來，比較 5 和基準(zhǔn)值，因?yàn)?5 > 4，所以將 5 放在基準(zhǔn)值的右邊。
5 > 4， 將5放在基準(zhǔn)值右邊
對(duì)整個(gè)序列進(jìn)行同樣操作后，所有小于基準(zhǔn)值的數(shù)字全都放到了基準(zhǔn)值的左邊，大于的則全都放在了右邊。
一輪排序完成后的結(jié)果
把基準(zhǔn)值放入序列
現(xiàn)在排序就分成了兩個(gè)子問題，分別再對(duì)基準(zhǔn)值左邊和右邊的數(shù)據(jù)進(jìn)行排序。
分解成了兩個(gè)子問題
兩邊的排序操作也和前面的一樣，也是使用快排算法，選取基準(zhǔn)值，把小于的數(shù)字放左邊大于的放右邊。
對(duì)子序列使用快速排序
子問題有可能會(huì)再分解成子問題，直到子問題里只剩下一個(gè)數(shù)字，再也無法分解出子問題的時(shí)候，整個(gè)序列的排序才算完成。
排序完成
因?yàn)榭焖倥判蛩惴ㄔ趯?duì)序列進(jìn)行排序的過程中會(huì)再次使用該算法，所以快速排序算法在實(shí)現(xiàn)時(shí)需要使用"遞歸”來實(shí)現(xiàn)。
快速排序的Go代碼實(shí)現(xiàn)
下面上一個(gè)用 Go 版本的快速排序算法的簡(jiǎn)單實(shí)現(xiàn)：
func quickSort(sequence []int, low int, high int) {
if high <= low {
return
}
j := partition(sequence, low, high)
quickSort(sequence, low, j-1)
quickSort(sequence, j+1, high)
}
// 進(jìn)行快速排序中的一輪排序
func partition(sequence []int, low int, high int) int {
i, j := low+1, high
for {
// 把頭元素作為基準(zhǔn)值 pivot
for sequence[i] < sequence[low] {
// i 坐標(biāo)從前往后訪問序列，如果位置上的值大于基準(zhǔn)值，停下來。
// 準(zhǔn)備和 j 坐標(biāo)訪問到的小于基準(zhǔn)值的值交換位置
i++
if i >= high {
break
}
}
for sequence[j] > sequence[low] {
// j 坐標(biāo)從后往前訪問序列，如果位置上的值小于基準(zhǔn)值，停下來。
// 和 i 坐標(biāo)指向的大于基準(zhǔn)值的值交換位置
j--
if j <= low {
break
}
}
if i >= j {
break
}
sequence[i], sequence[j] = sequence[j], sequence[i]
}
sequence[low], sequence[j] = sequence[j], sequence[low]
return j
}
每一輪快速排序都會(huì)經(jīng)歷下面這幾個(gè)步驟：
- 設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=待排序序列長(zhǎng)度 - 1。
- 以第一個(gè)數(shù)組元素作為基準(zhǔn)值 pivot(也可以是最后一個(gè)元素，或者是隨機(jī)的一個(gè)元素)。
- i 坐標(biāo)從開始向后訪問序列里的元素，即 i++，找到第一個(gè)大于 pivot 的位置 ，和 j 坐標(biāo)訪問到的小于基準(zhǔn)值的值交換位置。
- j 坐標(biāo)從末尾向前搜索，即j--，找到第一個(gè)小于 pivot 的位置，將i，j坐標(biāo)上的值進(jìn)行互換。
- 重復(fù)第3、4步，直到i=j，然后將 pivot 和 j 坐標(biāo)上的值互換，完成一輪排序，小于 pivot 的值都放在了它的左邊，大于的則放到了右邊。
重復(fù)進(jìn)行上面的過程，直到排序完成。最后我們可以生成一個(gè)隨機(jī)數(shù)序列對(duì)上面的快速排序函數(shù)進(jìn)行測(cè)試：
func main() {
rand.Seed(time.Now().Unix())
sequence := rand.Perm(34)
fmt.Printf("sequence before sort: %v", sequence)
quickSort(sequence, 0, len(sequence) - 1)
fmt.Printf("sequence after sort: %v", sequence)
}
快速排序的時(shí)間復(fù)雜度
分割子序列時(shí)需要選擇基準(zhǔn)值，如果每次選擇的基準(zhǔn)值都能使得兩個(gè)子序列的長(zhǎng)度為原本的一半，那么快速排序的運(yùn)行時(shí)間和歸并排序的一樣，都為 O(nlogn)。將序列對(duì)半分割 log2n 次之后，子序列里便只剩下一個(gè)數(shù)據(jù)，這時(shí)子序列的排序也就完成了。
因此，如果像下圖這樣一行行地展現(xiàn)根據(jù)基準(zhǔn)值分割序列的過程，那么總共會(huì)有 log2n 行。
快排分解序列的次數(shù)
每行中每個(gè)數(shù)字都需要和基準(zhǔn)值比較大小，因此每行所需的運(yùn)行時(shí)間為 O(n)。由此可知，整體的時(shí)間復(fù)雜度為 O(nlogn)。
如果運(yùn)氣不好，每次都選擇最小值作為基準(zhǔn)值，那么每次都需要把其他數(shù)據(jù)移到基準(zhǔn)值的右邊，遞歸執(zhí)行 n 行，運(yùn)行時(shí)間也就成了
。
所以真正應(yīng)用的時(shí)候基準(zhǔn)值的選取也比較講究，比如以中位數(shù)做基準(zhǔn)值：本輪排序序列的第一個(gè)、最后一個(gè)、中間位置三個(gè)數(shù)的中位數(shù)作為基準(zhǔn)值進(jìn)行排序。
