本文將對(duì)快速排序進(jìn)行深入的分析和介紹。通過學(xué)習(xí)本文，您將

八卦花絮

快速排序是由圖靈獎(jiǎng)獲得者、計(jì)算機(jī)語(yǔ)言設(shè)計(jì)大佬C. A. R. Hoare在他26歲時(shí)提出的。說起C. A. R. Hoare老爺爺，可能很多人的第一印象就是快速排序，但是快排僅僅是他人生中非常小的成就而已。例如，他在1978年提出的Communicating Sequential Processes(CSP)理論，則深深的影響了并行程序設(shè)計(jì)，Go語(yǔ)言中的Goroutine就是這種典范。

基本思想

快速排序的思想非常簡(jiǎn)單：對(duì)于一個(gè)數(shù)組S，我們選擇一個(gè)元素，稱為pivot。將數(shù)組S中小于等于pivot的元素放在S的左邊，大于等于pivot的元素放在S的右邊。左右兩部分分別記為S1和S2，然后我們遞歸的按上述方式對(duì)S1、S2進(jìn)行排序。

具體說來，我們維護(hù)兩個(gè)指針，采用兩邊掃描。從左到右掃描，當(dāng)遇到一個(gè)元素大于等于pivot時(shí)，暫停。從右到左掃描，當(dāng)遇到一個(gè)小于等于pivot元素時(shí)，暫停。然后交換這兩個(gè)元素。繼續(xù)掃描，直到兩個(gè)指針相遇或者交叉。

從直觀上看，每次遞歸處理的兩個(gè)子數(shù)組S1、S2的大小最好是相等或者接近的，這樣所花費(fèi)的時(shí)間最少。

實(shí)現(xiàn)細(xì)節(jié)

說起來容易，做起來難了。要想正確實(shí)現(xiàn)快速排序非常不容易，很容易犯錯(cuò)。簡(jiǎn)單的修改就可能導(dǎo)致程序死循環(huán)或者結(jié)果錯(cuò)誤。如果你一度感到很難在幾分鐘內(nèi)實(shí)現(xiàn)一個(gè)正確的快速排序，說明你是正常人。那些五分鐘內(nèi)就能把快速排序?qū)憣?duì)的，幾乎都是背代碼。

我在實(shí)現(xiàn)以下代碼時(shí)，就反復(fù)調(diào)試了十幾分鐘。而且，我會(huì)告訴你曾經(jīng)JDK的某個(gè)版本實(shí)現(xiàn)中都存在bug么？

在給出完整代碼之前，我們來考慮幾個(gè)非常重要的問題。

如何選擇pivot？

至少有幾種顯而易見的方法：

嘗試1:選擇數(shù)組中的第一個(gè)元素。成本低，但是當(dāng)輸入數(shù)組已經(jīng)有序時(shí)，將導(dǎo)致O($n^2$)的復(fù)雜度。例如S={1,2,3,4,5,6,7,8,9}，如果選擇第一個(gè)元素也就是1作為pivot，那么S1={1}, S2={2,3,4,5,6,7,8,9}，兩個(gè)子數(shù)組非常的不平衡。當(dāng)遞歸對(duì)S2排序時(shí)，選擇2也就是S2中第一個(gè)元素作為pivot排序時(shí)，又會(huì)將S2分成兩個(gè)極其不平衡的子數(shù)組。經(jīng)過簡(jiǎn)單分析可知，此時(shí)算法復(fù)雜度為O($n^2$)。因此這不是一個(gè)理想、健壯的方法。

嘗試2:隨機(jī)選擇一個(gè)。這種方法一般都能很好work，但是隨機(jī)子程序可能非常昂貴，這可能拖慢整個(gè)程序。

嘗試3:取中位數(shù)。取中位數(shù)可以保證S的兩個(gè)子數(shù)組是等大小的（或者相差1），但是計(jì)算中位數(shù)可不是一個(gè)輕輕松松的活兒，將會(huì)嚴(yán)重拖慢算法速度。

嘗試4:三數(shù)取中。嘗試3方法太昂貴，我們可以稍微改變下：取數(shù)組第一個(gè)元素、最后一個(gè)元素、中間元素這三個(gè)元素的中位數(shù)。

遇到相等的元素怎么辦？

左右掃描，如果遇到和pivot相等的元素怎么辦？是暫停掃描還是繼續(xù)掃描？

首先，兩個(gè)方向采取的策略應(yīng)該是一樣的，也就是要么都暫停（然后交換），要么都繼續(xù)掃描。否則將導(dǎo)致兩個(gè)子數(shù)組不平衡。

其次，為了更好分析這個(gè)問題，我們不妨考慮所有元素都相同的情形。如果我們遇到和pivot相等的時(shí)候不停止，那么從左到右掃描時(shí)，兩指針將相遇，此次過程結(jié)束。結(jié)果呢？什么都沒做，卻得到了兩個(gè)大小極其不均衡的數(shù)組。算法時(shí)間復(fù)雜度為O($n^2$)。如果我們選擇遇到相等元素時(shí)停止掃描，然后交換，那么雖然看上去交換的次數(shù)變多了，但是我們將得到大小相等（或者差1）的兩個(gè)子數(shù)組。算法的時(shí)間復(fù)雜度為O($nlgn$)。

因此，遇到和pivot相等的元素時(shí)候我們都暫停掃描，交換元素后繼續(xù)，直到指針相遇或者交叉。

小數(shù)組怎么處理？

隨著不斷的遞歸，待排序的子數(shù)組大小越來越小，所含元素越來越少。當(dāng)子數(shù)組所含元素較少（比如說，20個(gè)）時(shí)，由于它們已經(jīng)基本有序，我們改變策略，對(duì)它們改用插入排序。這也方便了三數(shù)取中策略的實(shí)現(xiàn)，否則我們?cè)谌龜?shù)取中的時(shí)候還得特殊考慮子數(shù)組有0個(gè)、1個(gè)、2個(gè)元素的情形。當(dāng)子數(shù)組多大時(shí)我們轉(zhuǎn)換排序方法呢？這個(gè)最優(yōu)值就依賴于體系結(jié)構(gòu)了。為了找到你系統(tǒng)中它的最優(yōu)值，請(qǐng)多測(cè)試！測(cè)試！測(cè)試！

完整實(shí)現(xiàn)

#define INLINE __attribute__((always_inline))
template<typename T>
class CompareOperator
{
public:
  INLINE bool operator() (const T &a, const T &b) { return a < b;}
};
template<typename T, typename CallBack, int64_t threshold = 20>
class YedisSort
{
public:
  static void sort(T *data, int64_t size);
private:
  static void sort_(T *data, int64_t left, int64_t right, const CallBack &cb);
  static void insertion_sort(T *data, int64_t left, int64_t right, const CallBack &cb);
  static const T& get_pivot(T *data, int64_t left, int64_t right, const CallBack &cb);
};
template<typename T, typename CallBack, int64_t threshold>
INLINE void YedisSort<T, CallBack, threshold>::sort(T *data, int64_t size)
{
  CallBack cb;
  sort_(data, 0, size - 1, cb);
}

template<typename T, typename CallBack, int64_t threshold>
void YedisSort<T, CallBack, threshold>::sort_(T *data, int64_t left, int64_t right, const CallBack &cb)
{
  if(right - left > threshold) {
    const T& pivot = get_pivot(data, left, right, cb);
    int64_t i = left;
    int64_t j = right - 1;
    while(true) {
      do
      {
        ++i;
      }while(cb(data[i], pivot));
      do
      {
        --j;
      }while(cb(pivot, data[j]));
      if (i < j) {
        std::swap(data[i], data[j]);
      } else {
        break;
      }
    }
    std::swap(data[i], data[right - 1]);//restore pivot
    sort_(data, left, i - 1, cb);
    sort_(data, i + 1, right, cb);
  } else {
    insertion_sort(data, left, right, cb);
  }
}

template<typename T, typename CallBack, int64_t threshold>
INLINE void YedisSort<T, CallBack, threshold>::insertion_sort(T *data, int64_t left, int64_t right, const CallBack &cb)
{
  int64_t begin = left + 1;
  int64_t end = right + 1;
  for (int64_t i = begin; i < end; i++) {
    //insert data[i]. data[left to i-1] are ordered already
    int64_t j = i - 1;
    T tmp = data[i];
    while(j >-1 && cb(tmp, data[j])) {
      data[j+1] = data[j];
      j--;
    }
    data[j+1] = tmp;
  }
}

template<typename T, typename CallBack, int64_t threshold>
INLINE const T& YedisSort<T, CallBack, threshold>::get_pivot(T *data, int64_t left, int64_t right, const CallBack &cb)
{
  int64_t mid = (left + right) / 2;
  if (cb(data[mid], data[left])) {
    std::swap(data[mid], data[left]);
  }
  if (cb(data[right], data[mid])) {
    std::swap(data[mid], data[right]);
  }
  if (cb(data[mid], data[left])) {
    std::swap(data[mid], data[left]);
  }
  //Store pivot there to facilitate bound processing in sort_
  //data[right - 1] <= data[right]
  std::swap(data[mid], data[right - 1]);
  return data[right - 1];
}

我們把以上實(shí)現(xiàn)的快速排序稱為YedisSort。

測(cè)試結(jié)果

測(cè)試程序已經(jīng)放到了github上，可以從 這里 下載。

我們pk的對(duì)象包括STL中的sort，以及C語(yǔ)言里大名鼎鼎的qsort。

測(cè)試結(jié)果：

1000W個(gè)隨機(jī)打亂的32位無符號(hào)整數(shù)

開啟O2優(yōu)化（單位：秒）：

sort: 1.06

YedisSort: 1.20

qsort: 2.08

未開啟O2優(yōu)化（單位：秒）：

sort: 3.29

YedisSort: 2.93

qsort: 2.91

1000W個(gè)相同的整數(shù)

開啟O2優(yōu)化（單位：秒）：

sort: 0.23

YedisSort: 0.27

qsort: 0.59

未開啟O2優(yōu)化（單位：秒）：

sort: 2.60

YedisSort: 1.56

qsort: 0.76

什么結(jié)論？

沒開優(yōu)化，那么所需時(shí)間 qsort < YedisSort < sort

開了優(yōu)化，那么所需時(shí)間 sort < YedisSort < qsort

為什么sort可以這么叼？據(jù)說它綜合了插入排序、快速排序和堆排序。這讓我想起了推薦和廣告比賽里，有些隊(duì)伍利用Ensemble Learning沒節(jié)操地堆了幾百個(gè)model。。。

Further Thinking

1，64行的 while(j >-1 && cb(tmp, data[j])) 能否改為 while(j >-1 && !cb(data[j], tmp)) ？ 同理，36和40行能否作相應(yīng)的改動(dòng)？

2，30-46行能否改為：

int64_t i = left + 1;
int64_t j = right - 2;
while(true) {
  while(cb(data[i], pivot)) {
    ++i;
  }
  while(cb(pivot, data[j])) {
    --j;
  }
  if (i < j) {
    std::swap(data[i], data[j]);
  } else {
    break;
  }
}

深入分析這樣的case，將會(huì)對(duì)編寫正確的快速排序的困難性有更深的體會(huì)，雖然我們已經(jīng)有循環(huán)不變式這個(gè)強(qiáng)大的工具。

3，快速排序所需的棧空間是多少？能否進(jìn)一步優(yōu)化？

4，YedisSort的時(shí)間復(fù)雜度是多少？O($n^2$)還是O($nlgn$)？如果是前者，那么，什么情況下是二次的？