实现原理

快速排序是一种分治算法，排序方式是当两个子数组都有序的时候整个数组也就有序了。归并排序中，一个数组被一分为二，快速排序中 partition 的位置取决于数组的内容。

切分位置

切分位置要满足三个条件：

  1. 对于某个j，a[j] 已经确定
  2. a[lo] 到 a[j - 1] 中的元素都不大于 a[j]
  3. a[j+1] 到 a[hi] 中的元素都不小于 a[j]

切分算法

随意的取 a[lo] 作为切分元素，向右扫描知道找到一个大于等于它的元素 a[i]，再从 a[hi] 开始找知道找到一个小于等于它的元素。如果 i < j 则交换两个元素的内容继续扫描，知道 i >= j 位置。交换 a[lo] 和 a[j] 的内容。
这样就能保证 a[j] 的左边都是小于它的元素，a[j] 的右边都是大于它的元素。

代码实现

  1. func partition(a []int, lo, hi int) int {
  2.   i, j := lo + 1, hi
  3.   v := a[lo]
  5.   for {
  6.     for a[i] < v {
  7.       i++
  8.       if i == hi {
  9.         break
  10.       }
  11.     }
  13.     for v < a[j] {
  14.       j--
  15.       if j == lo {
  16.         break
  17.       }
  18.     }
  20.     if i >= j {
  21.       break
  22.     }
  24.     exch(a, i, j)
  25.   }
  27.   // 交换两个元素，确保切分位置的正确
  28.   exch(a, lo, j)
  29.   return j
  30. }
  33. func sort(a []int, lo, hi int) {
  34.   if hi <= lo {
  35.     return
  36.   }
  38.   j := partition(a, lo, hi)
  39.   sort(a, lo, j - 1)
  40.   sort(a, j + 1, hi)
  41. }