深入解析快速排序

本文将对快速排序进行深入的分析和介绍。通过学习本文，您将

  • 秒杀快速排序面试
  • 掌握高效实现快排
  • 加深范型编程意识

八卦花絮

快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷，可能很多人的第一印象就是快速排序，但是快排仅仅是他人生中非常小的成就而已。例如，他在1978年提出的Communicating Sequential Processes(CSP)理论，则深深的影响了并行程序设计，Go语言中的Goroutine就是这种典范。

基本思想

快速排序的思想非常简单：对于一个数组S，我们选择一个元素，称为pivot。将数组S中小于等于pivot的元素放在S的左边，大于等于pivot的元素放在S的右边。左右两部分分别记为S1和S2，然后我们递归的按上述方式对S1、S2进行排序。

具体说来，我们维护两个指针，采用两边扫描。从左到右扫描，当遇到一个元素大于等于pivot时，暂停。从右到左扫描，当遇到一个小于等于pivot元素时，暂停。然后交换这两个元素。继续扫描，直到两个指针相遇或者交叉。

从直观上看，每次递归处理的两个子数组S1、S2的大小最好是相等或者接近的，这样所花费的时间最少。

实现细节

说起来容易，做起来难了。要想正确实现快速排序非常不容易，很容易犯错。简单的修改就可能导致程序死循环或者结果错误。如果你一度感到很难在几分钟内实现一个正确的快速排序，说明你是正常人。那些五分钟内就能把快速排序写对的，几乎都是背代码。

我在实现以下代码时，就反复调试了十几分钟。而且，我会告诉你曾经JDK的某个版本实现中都存在bug么？

在给出完整代码之前，我们来考虑几个非常重要的问题。

如何选择pivot？

至少有几种显而易见的方法：

尝试1:选择数组中的第一个元素。成本低，但是当输入数组已经有序时，将导致O($n^2$)的复杂度。例如S={1,2,3,4,5,6,7,8,9}，如果选择第一个元素也就是1作为pivot，那么S1={1}, S2={2,3,4,5,6,7,8,9}，两个子数组非常的不平衡。当递归对S2排序时，选择2也就是S2中第一个元素作为pivot排序时，又会将S2分成两个极其不平衡的子数组。经过简单分析可知，此时算法复杂度为O($n^2$)。因此这不是一个理想、健壮的方法。

尝试2:随机选择一个。这种方法一般都能很好work，但是随机子程序可能非常耗时，这可能拖慢整个程序。

尝试3:取中位数。取中位数可以保证S的两个子数组是等大小的（或者相差1），但是计算中位数可不是一个轻轻松松的活儿，将会严重拖慢算法速度。

尝试4:三数取中。尝试3方法太昂贵，我们可以稍微改变下：取数组第一个元素、最后一个元素、中间元素这三个元素的中位数。

遇到相等的元素怎么办？

左右扫描，如果遇到和pivot相等的元素怎么办？是暂停扫描还是继续扫描？

首先，两个方向采取的策略应该是一样的，也就是要么都暂停（然后交换），要么都继续扫描。否则将导致两个子数组不平衡。

其次，为了更好分析这个问题，我们不妨考虑所有元素都相同的情形。如果我们遇到和pivot相等的时候不停止，那么从左到右扫描时，两指针将相遇，此次过程结束。结果呢？什么都没做，却得到了两个大小极其不均衡的数组。算法时间复杂度为O($n^2$)。如果我们选择遇到相等元素时停止扫描，然后交换，那么虽然看上去交换的次数变多了，但是我们将得到大小相等（或者差1）的两个子数组。算法的时间复杂度为O($nlgn$)。

因此，遇到和pivot相等的元素时候我们都暂停扫描，交换元素后继续，直到指针相遇或者交叉。

小数组怎么处理？

随着不断的递归，待排序的子数组大小越来越小，所含元素越来越少。当子数组所含元素较少（比如说，20个）时，由于它们已经基本有序，我们改变策略，对它们改用插入排序。这也方便了三数取中策略的实现，否则我们在三数取中的时候还得特殊考虑子数组有0个、1个、2个元素的情形。当子数组多大时我们转换排序方法呢？这个最优值就依赖于体系结构了。为了找到你系统中它的最优值，请多测试！测试！测试！

完整实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

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

template<typename T, typename CompareOperator, int64_t threshold>
void SoupenSort<T, CompareOperator, threshold>::sort_(T *data, int64_t left, int64_t right, const CompareOperator &co)
{
  if(right - left > threshold) {
    const T& pivot = get_pivot(data, left, right, co);
    int64_t i = left;
    int64_t j = right - 1;
    while(true) {
      do
      {
        ++i;
      }while(co(data[i], pivot));
      do
      {
        --j;
      }while(co(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, co);
    sort_(data, i + 1, right, co);
  } else {
    insertion_sort(data, left, right, co);
  }
}

template<typename T, typename CompareOperator, int64_t threshold>
INLINE void SoupenSort<T, CompareOperator, threshold>::insertion_sort(T *data, int64_t left, int64_t right, const CompareOperator &co)
{
  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 && co(tmp, data[j])) {
      data[j+1] = data[j];
      j--;
    }
    data[j+1] = tmp;
  }
}

template<typename T, typename CompareOperator, int64_t threshold>
INLINE const T& SoupenSort<T, CompareOperator, threshold>::get_pivot(T *data, int64_t left, int64_t right, const CompareOperator &co)
{
  int64_t mid = (left + right) / 2;
  if (co(data[mid], data[left])) {
    std::swap(data[mid], data[left]);
  }
  if (co(data[right], data[mid])) {
    std::swap(data[mid], data[right]);
  }
  if (co(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];
}

我们把以上实现的快速排序称为SoupenSort。是的，90行不到。

测试结果

我们pk的对象包括STL中的sort，以及C语言里大名鼎鼎的qsort。

我们的平台是Ubuntu 64位系统 + gcc 4.8

测试结果：

1000W个随机打乱的32位无符号整数

开启O2优化（单位：秒）：

sort SoupenSort qsort
1.06 1.20 2.08

未开启O2优化（单位：秒）：

sort SoupenSort qsort
3.29 2.93 2.91

1000W个相同的整数

开启O2优化（单位：秒）：

sort SoupenSort qsort
0.23 0.27 0.59

未开启O2优化（单位：秒）：

sort SoupenSort qsort
2.60 1.56 0.76

什么结论？

没开优化，那么所需时间 qsort < SoupenSort < sort

开了优化，那么所需时间 sort < SoupenSort < qsort

为什么sort可以这么叼？据说它综合了插入排序、快速排序和堆排序。这让我想起了推荐和广告比赛里，有些队伍利用Ensemble Learning没节操地堆了几百个model。。。

Further Thinking

1，64行的 while(j >-1 && co(tmp, data[j])) 能否改为 while(j >-1 && !co(data[j], tmp)) ？ 同理，36和40行能否作相应的改动？

2，30-46行能否改为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

深入分析这样的case，将会对编写正确的快速排序的困难性有更深的体会，虽然我们已经有循环不变式这个强大的工具。

3，快速排序所需的栈空间是多少？能否进一步优化？

4，SoupenSort的时间复杂度是多少？O($n^2$)还是O($nlgn$)？如果是前者，那么，什么情况下是二次的？