很多面試題的解答都是以排序為基礎(chǔ)的，如果我們寫出一個的算法，大概率要被掛，今天寫個快排的基礎(chǔ)文章，后面看情況再把歸并和堆排序?qū)懸粚懀劣谶x擇排序、冒泡排序這種時間復(fù)雜度高的就不寫了，有興趣的可以找書自己看一下。

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

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

快速排序的思想

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

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

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

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

快排的過程

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

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

假定有如下待排序序列：

待排序序列

首先在序列中隨機選擇一個基準值，這里選擇了 4。

選擇基準值 pivot

將其他數(shù)字和基準值進行比較，小于基準值的往左移，大于基準值的往右移。

首先比較第一個元素 3 和基準值4，因為 3 < 4, 所以將 3放在基準值的左邊。

首先比較 3 和基準值4，因為 3 < 4, 所以將 3放在基準值的左邊

接下來，比較 5 和基準值，因為 5 > 4，所以將 5 放在基準值的右邊。

5 > 4， 將5放在基準值右邊

對整個序列進行同樣操作后，所有小于基準值的數(shù)字全都放到了基準值的左邊，大于的則全都放在了右邊。

一輪排序完成后的結(jié)果

把基準值放入序列

現(xiàn)在排序就分成了兩個子問題，分別再對基準值左邊和右邊的數(shù)據(jù)進行排序。

分解成了兩個子問題

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

對子序列使用快速排序

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

排序完成

因為快速排序算法在對序列進行排序的過程中會再次使用該算法，所以快速排序算法在實現(xiàn)時需要使用"遞歸”來實現(xiàn)。

快速排序的Go代碼實現(xiàn)

下面上一個用 Go 版本的快速排序算法的簡單實現(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)
}

// 進行快速排序中的一輪排序
func partition(sequence []int, low int, high int) int {
 i, j := low+1, high
 for {
  // 把頭元素作為基準值 pivot
  for sequence[i] < sequence[low] {
   // i 坐標(biāo)從前往后訪問序列，如果位置上的值大于基準值，停下來。
   // 準備和 j 坐標(biāo)訪問到的小于基準值的值交換位置
   i++
   if i >= high {
    break
   }
  }
  for sequence[j] > sequence[low] {
   // j 坐標(biāo)從后往前訪問序列，如果位置上的值小于基準值，停下來。
   // 和 i 坐標(biāo)指向的大于基準值的值交換位置
   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
}

每一輪快速排序都會經(jīng)歷下面這幾個步驟：

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

重復(fù)進行上面的過程，直到排序完成。最后我們可以生成一個隨機數(shù)序列對上面的快速排序函數(shù)進行測試：

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)
}

快速排序的時間復(fù)雜度

分割子序列時需要選擇基準值，如果每次選擇的基準值都能使得兩個子序列的長度為原本的一半，那么快速排序的運行時間和歸并排序的一樣，都為 O(nlogn)。將序列對半分割 log2n 次之后，子序列里便只剩下一個數(shù)據(jù)，這時子序列的排序也就完成了。

因此，如果像下圖這樣一行行地展現(xiàn)根據(jù)基準值分割序列的過程，那么總共會有 log2n 行。

快排分解序列的次數(shù)

每行中每個數(shù)字都需要和基準值比較大小，因此每行所需的運行時間為 O(n)。由此可知，整體的時間復(fù)雜度為 O(nlogn)。

如果運氣不好，每次都選擇最小值作為基準值，那么每次都需要把其他數(shù)據(jù)移到基準值的右邊，遞歸執(zhí)行 n 行，運行時間也就成了。

所以真正應(yīng)用的時候基準值的選取也比較講究，比如以中位數(shù)做基準值：本輪排序序列的第一個、最后一個、中間位置三個數(shù)的中位數(shù)作為基準值進行排序。