很多面試題的解答都是以排序?yàn)榛A(chǔ)的，如果我們寫(xiě)出一個(gè)的算法，大概率要被掛，今天寫(xiě)個(gè)快排的基礎(chǔ)文章，后面看情況再把歸并和堆排序?qū)懸粚?xiě)，至于選擇排序、冒泡排序這種時(shí)間復(fù)雜度高的就不寫(xiě)了，有興趣的可以找書(shū)自己看一下。

文中算法的實(shí)現(xiàn)是用 Go 寫(xiě)了一個(gè)比較簡(jiǎn)單的快速排序，方便大家理解(旁邊畫(huà)外音：其實(shí)是他好幾年沒(méi)面試了，太厲害的他也寫(xiě)不出來(lái))。

關(guān)于更優(yōu)秀的代碼實(shí)現(xiàn)，可以在評(píng)論區(qū)里發(fā)出來(lái)一起學(xué)習(xí)，相信咱們讀者里一定是臥虎藏龍，有不少算法大拿。

快速排序的思想

快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值(pivot)，然后將除了基準(zhǔn)值之外的數(shù)分為 "比基準(zhǔn)值小的數(shù)" 和 "比基準(zhǔn)值大的數(shù)" 這兩個(gè)類(lèi)別，再將其排列成以下形式。

【比基準(zhǔn)值小的數(shù)】 基準(zhǔn)值 【比基準(zhǔn)值大的數(shù)】

接著，繼續(xù)對(duì)兩個(gè)序列 "【】"中的數(shù)據(jù)進(jìn)行排序之后，整體的排序便完成了。對(duì)基準(zhǔn)值左右兩側(cè)的序列排序時(shí)，同樣也會(huì)使用快速排序。

快速排序是一種"分治法"，將原本的問(wèn)題分解成兩個(gè)子問(wèn)題—— 比基準(zhǔn)值小的數(shù)和比基準(zhǔn)值大的數(shù)，然后再分別解決這兩個(gè)子問(wèn)題。解決子問(wèn)題的時(shí)候會(huì)再次使用快速排序，只有在子問(wèn)題里只剩下一個(gè)數(shù)字的時(shí)候，排序才算完成。

快排的過(guò)程

下面我們用示意圖更好地理解一下快速排序?qū)σ粋€(gè)序列進(jìn)行排序的過(guò)程。

圖例出自—《我的第一本算法書(shū)》。

假定有如下待排序序列：

待排序序列

首先在序列中隨機(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)值的左邊

接下來(lái)，比較 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è)子問(wèn)題，分別再對(duì)基準(zhǔn)值左邊和右邊的數(shù)據(jù)進(jìn)行排序。

分解成了兩個(gè)子問(wèn)題

兩邊的排序操作也和前面的一樣，也是使用快排算法，選取基準(zhǔn)值，把小于的數(shù)字放左邊大于的放右邊。

對(duì)子序列使用快速排序

子問(wèn)題有可能會(huì)再分解成子問(wèn)題，直到子問(wèn)題里只剩下一個(gè)數(shù)字，再也無(wú)法分解出子問(wèn)題的時(shí)候，整個(gè)序列的排序才算完成。

排序完成

因?yàn)榭焖倥判蛩惴ㄔ趯?duì)序列進(jìn)行排序的過(guò)程中會(huì)再次使用該算法，所以快速排序算法在實(shí)現(xiàn)時(shí)需要使用"遞歸”來(lái)實(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)從前往后訪問(wèn)序列，如果位置上的值大于基準(zhǔn)值，停下來(lái)。
   // 準(zhǔn)備和 j 坐標(biāo)訪問(wèn)到的小于基準(zhǔn)值的值交換位置
   i++
   if i >= high {
    break
   }
  }
  for sequence[j] > sequence[low] {
   // j 坐標(biāo)從后往前訪問(wèn)序列，如果位置上的值小于基準(zhǔn)值，停下來(lái)。
   // 和 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è)步驟：

1. 設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=待排序序列長(zhǎng)度 - 1。
2. 以第一個(gè)數(shù)組元素作為基準(zhǔn)值 pivot(也可以是最后一個(gè)元素，或者是隨機(jī)的一個(gè)元素)。
3. i 坐標(biāo)從開(kāi)始向后訪問(wèn)序列里的元素，即 i++，找到第一個(gè)大于 pivot 的位置 ，和 j 坐標(biāo)訪問(wèn)到的小于基準(zhǔn)值的值交換位置。
4. j 坐標(biāo)從末尾向前搜索，即j--，找到第一個(gè)小于 pivot 的位置，將i，j坐標(biāo)上的值進(jìn)行互換。
5. 重復(fù)第3、4步，直到i=j，然后將 pivot 和 j 坐標(biāo)上的值互換，完成一輪排序，小于 pivot 的值都放在了它的左邊，大于的則放到了右邊。

重復(fù)進(jìn)行上面的過(guò)程，直到排序完成。最后我們可以生成一個(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)值分割序列的過(guò)程，那么總共會(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)行排序。