深入解析快速排序(Quick Sort)

codingparty 2016-03-10

展開全文

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

秒殺快速排序面試
掌握高效實現(xiàn)快排
加深范型編程意識

八卦花絮

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

基本思想

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

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

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

實現(xiàn)細節(jié)

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

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

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

如何選擇pivot？

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

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

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

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

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

遇到相等的元素怎么辦？

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

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

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

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

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

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

完整實現(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];
}

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

測試結(jié)果

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

我們pk的對象包括STL中的sort，以及C語言里大名鼎鼎的qsort。

測試結(jié)果：

1000W個隨機打亂的32位無符號整數(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個相同的整數(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)化，那么所需時間 qsort < YedisSort < sort

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

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

Further Thinking

1，64行的 while(j >-1 && cb(tmp, data[j])) 能否改為 while(j >-1 && !cb(data[j], tmp)) ？同理，36和40行能否作相應(yī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;
  }
}