我觉得在一般场合，单线程下快速排序是最快的，尽管它的时间复杂度为O(nlogn)，它甚至比时间复杂度为O(n)的基数排序、桶排序和计数排序都快一些。
如果对字符窜排序，即使快排的仅仅是字符窜的指针(避免拷贝字符窜)，burst sort还是比快速排序快一些。
快速排序的版本很多，常见的有C库函数qsort，C++STL中的sort(多个版本)，还是大学书上的臃肿快速排序的实现。
这里介绍SGI STL版本的快速排序，它需要插入排序，堆排序和一般意义上的快速排序。

先看直接插入排序

直接插入排序的时间复杂度为O(n2)，最好情况下为O(n)，它的优势是当序列很短或基本有序时排序速度比较快。此外，直接插入排序仅需要一个元素的额外存储空间，空间复杂度为O(1)，很节约内存。

假设有一个序列需要排序成升序，该序列含有n个元素，排序时从第i(i = 1, 2, …, n-1，注意C语言下标从0开始，因此存在第0个元素，在这点上，应该顺应编程习惯，而不是通俗意义上的第1个，第2个…)个元素开始跟它前面的元素逐个比较，直到比较到第j(j = 0, 1, …, i-1)个，如果该(第i个)元素值比它前面的(第j个)元素值小，但不比第j-1(j = 1, 2, …, i-1)个元素值小，则把该元素插入到第j个元素的前面(位于下标区间[j, i)的所有元素需要事先后移一个元素位置)。

以一个随机整数序列为例，插入排序的过程见下表。

21 16 27 57 31 46 48 63 01 32 26 98 46 95 69 47

待排序序列

16 21  27 57 31 46 48 63 01 32 26 98 46 95 69 47 

16到位

16 21 27 57 31 46 48 63 01 32 26 98 46 95 69 47

27不动

16 21 27 57 31 46 48 63 01 32 26 98 46 95 69 47 

57不动

16 21 27 31 57 46 48 63 01 32 26 98 46  95 69 47

31到位

16 21 27 31 46 57 48 63 01 32 26 98 46 95 69 47 

46 到位

16 21 27 31 46 48 57 63 01 32 26 98 46 95 69 47 

48 到位

16 21 27 31 46 48 57 63 01 32 26 98 46 95 69 47

63不动

01 16 21 27 31 46 48 57 63 32 26 98 46 95 69 47 

01到位

01 16 21 27 31 32 46 48 57 63 26 98 46 95 69 47 

32 到位

01 16 21 26 27 31 32 46 48 57 63 98 46 95 69 47 

26到位

01 16 21 26 27 31 32 46 48 57 63 98 46 95 69 47 

98不动

01 16 21 26 27 31 32 46 46 48 57 63 98 95 69 47 

46到位

01 16 21 26 27 31 32 46 46 48 57 63 95 98 69 47

95到位

01 16 21 26 27 31 32 46 46 48 57 63 69 95 98 47 

69到位

01 16 21 26 27 31 32 46 46 47 48 57 63 69 95 98

47到位，完毕

 1 template <typename RandomIterator, typename T, typename Compare>
 2 void unguarded_linear_insert(RandomIterator last,
 3                              T value,
 4                              Compare cmp)
 5 {
 6   RandomIterator next = last - 1;
 7   while (cmp(value, *next))
 8   {
 9     *last = *next;
10     last = next;
11     --next;
12   }
13   *last = value;
14 }
15 
16 template <typename RandomIterator, typename T, typename Compare>
17 
18 inline void linear_insert(RandomIterator first, RandomIterator last,
19                                  T value,
20                                  Compare cmp)
21 {
22   if(cmp(value, *first))
23   {
24     for(; first != last; --last)
25       *last = *(last - 1);
26     *first = value;
27 
28   }
29   else unguarded_linear_insert(last, value, cmp);
30 }
31 
32 template <typename RandomIterator, typename Compare>
33 void insertion_sort(RandomIterator first, RandomIterator last,
34                             Compare cmp)
35 {
36   if(first == last) return;
37   for(RandomIterator i = first + 1; i != last; ++i)
38     linear_insert(first, i, *i, cmp);
39 }
40 
41 
42 template <typename RandomIterator, typename Compare>
43 void unguarded_insertion_sort(RandomIterator first, RandomIterator last,
44                                             Compare cmp)
45 {
46   for(RandomIterator i = first; i != last; ++i)
47     unguarded_linear_insert(i, *i, cmp);
48 }
49 
50 
51 template <typename RandomIterator, typename Compare>
52 void final_insertion_sort(RandomIterator first, RandomIterator last,
53                                    Compare cmp)
54 {
55   const int Insertion_threshold = 16;
56   if(last - first > Insertion_threshold)
57   {
58     insertion_sort(first, first + Insertion_threshold, cmp);
59     unguarded_insertion_sort(first + Insertion_threshold, last, cmp);
60 
61   }
62   else insertion_sort(first, last, cmp);
63 }
再看堆排序

堆排序的时间复杂度为O(nlogn)，空间复杂度O(1)，尽管平均速度比插入排序快得多，但在需要排序的一般场合，几乎见不到它的应用，因为跟快速排序和稳定排序比起来，它要显著慢一些。问题是，很多时候我们并不需要整个序列有序，仅仅需要从这个序列中找出一部分最大或最小的值。这种场合，堆排序十分擅长。

原理如下，来自

http://en.wikipedia.org/wiki/Heapsort

 

Heap swap elements delete element sorted array details
8, 6, 7, 4, 5, 3, 2, 1 8, 1

swap 8 and 1 in order to delete 8 from heap
1, 6, 7, 4, 5, 3, 2, 8
8
delete 8 from heap and add to sorted array
1, 6, 7, 4, 5, 3, 2 1, 7
8 swap 1 and 7 as they are not in order in the heap
7, 6, 1, 4, 5, 3, 2 1, 3
8 swap 1 and 3 as they are not in order in the heap
7, 6, 3, 4, 5, 1, 2 7, 2
8 swap 7 and 2 in order to delete 7 from heap
2, 6, 3, 4, 5, 1, 7
7 8 delete 7 from heap and add to sorted array
2, 6, 3, 4, 5, 1 2, 6
7, 8 swap 2 and 6 as thay are not in order in the heap
6, 2, 3, 4, 5, 1 2, 5
7, 8 swap 2 and 5 as they are not in order in the heap
6, 5, 3, 4, 2, 1 6, 1
7, 8 swap 6 and 1 in order to delete 6 from heap
1, 5, 3, 4, 2, 6
6 7, 8 delete 6 from heap and add to sorted array
1, 5, 3, 4, 2 1, 5
6, 7, 8 swap 1 and 5 as they are not in order in the heap
5, 1, 3, 4, 2 1, 4
6, 7, 8 swap 1 and 4 as they are not in order in the heap
5, 4, 3, 1, 2 5, 2
6, 7, 8 swap 5 and 2 in order to delete 5 from heap
2, 4, 3, 1, 5
5 6, 7, 8 delete 5 from heap and add to sorted array
2, 4, 3, 1 2, 4
5, 6, 7, 8 swap 2 and 4 as they are not in order in the heap
4, 2, 3, 1 4, 1
5, 6, 7, 8 swap 4 and 1 in order to delete 4 from heap
1, 2, 3, 4
4 5, 6, 7, 8 delete 4 from heap and add to sorted array
1, 2, 3 1, 3
4, 5, 6, 7, 8 swap 1 and 3 as they are not in order in the heap
3, 2, 1 3, 1
4, 5, 6, 7, 8 swap 3 and 1 in order to delete 3 from heap
1, 2, 3
3 4, 5, 6, 7, 8 delete 3 from heap and add to sorted array
1, 2 1, 2
3, 4, 5, 6, 7, 8 swap 1 and 2 as they are not in order in the heap
2, 1 2, 1
3, 4, 5, 6, 7, 8 swap 2 and 1 in order to delete 2 from heap
1, 2
2 3, 4, 5, 6, 7, 8 delete 2 from heap and add to sorted array
1
1 2, 3, 4, 5, 6, 7, 8 delete 1 from heap and add to sorted array



1, 2, 3, 4, 5, 6, 7, 8 completed

 

 1 template <typename RandomIterator, typename T, typename Compare>
 2 void push_heap_aux(RandomIterator first, int hole, int top, T value, Compare cmp)
 3 {
 4   int parent = (hole - 1) >> 1;
 5   while(hole > top && cmp(*(first + parent), value))
 6   {
 7     *(first + hole) = *(first + parent);
 8     hole = parent;
 9     parent = (hole - 1) >> 1;
10   }
11   *(first + hole) = value;
12 }
13 
14 template <typename RandomIterator, typename Compare>
15 inline void push_heap(RandomIterator first, RandomIterator last, Compare cmp)
16 {
17   push_heap_aux(first, (last - first) - 1, 0, *(last - 1), cmp);
18 }
19 
20 template <typename RandomIterator, typename T, typename Compare>
21 void adjust_heap(RandomIterator first, int hole, int len, T value, Compare cmp)
22 {
23   int top = hole;
24   int rchild = (hole << 1) + 2;
25   while(rchild < len)
26   {
27     if(cmp(*(first + rchild), *(first + (rchild - 1))))
28       --rchild;
29     *(first + hole) = *(first + rchild);
30     hole = rchild;
31     rchild = (rchild + 1) << 1;
32   }
33   if(rchild == len)
34   {
35     *(first + hole) = *(first + (rchild - 1));
36     hole = rchild - 1;
37   }
38   push_heap_aux(first, hole, top, value, cmp);
39 }
40 
41 template <typename RandomIterator, typename T, typename Compare>
42 inline void pop_heap_aux(RandomIterator first, RandomIterator last,
43                          RandomIterator result, T value, Compare cmp)
44 {
45   *result = *first;
46   adjust_heap(first, 0, last - first, value, cmp);
47 }
48 
49 template <typename RandomIterator, typename Compare>
50 inline void pop_heap(RandomIterator first, RandomIterator last, Compare cmp)
51 {
52   pop_heap_aux(first, last - 1, last - 1, *(last - 1), cmp);
53 }
54 
55 template <typename RandomIterator, typename Compare>
56 void make_heap(RandomIterator first, RandomIterator last, Compare cmp)
57 {
58   if(last - first < 2)
59         return;
60   int len = last - first, parent = (len - 2) >> 1;
61   while(true)
62   {
63     adjust_heap(first, parent, len, *(first + parent), cmp);
64     if(0 == parent)
65             break;
66     --parent;
67   }
68 }
69 
70 template <typename RandomIterator, typename Compare>
71 void sort_heap(RandomIterator first, RandomIterator last, Compare cmp)
72 {
73   for(; last - first > 1; --last)
74     pop_heap(first, last, cmp);
75 }
76 
77 template <typename RandomIterator, typename Compare>
78 void partial_sort(RandomIterator first, RandomIterator middle,
79                                     RandomIterator last, Compare cmp)
80 {
81   make_heap(first, middle, cmp);
82   for(RandomIterator i = middle; i < last; ++i)
83     if(cmp(*i, *first))
84       pop_heap_aux(first, middle, i, *i, cmp);
85   sort_heap(first, middle, cmp);
86 }

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)最坏情况下的时间复杂度为O(n2)，空间复杂度O(n)。在C++标准库的实现过程中，为了保证快速排序的速度，用堆排序对快速排序做了优化，即使在最坏情况下，sort仍然可以维持O(nlogn)的时间复杂度，空间复杂度则不会超过O(logn)。在一般性应用场合，快速排序不会愧对它的名字，尽管时间复杂度为O(nlogn)，但常数因子很小，因此排序速度比其它时间复杂度为O(nlogn)的堆排序和归并排序要快一些，甚至超越了理论上比它快的基数排序和计数排序以及桶排序，这后三种排序的时间复杂度理论值可是O(n)哦。C++继承了C库，因此C库里的qsort也被继承下来，只不过sort要比qsort排序速度快得多。

对于一个无需序列而言，当我们需要把它变成一个升序序列时，可以把它一分为二，使左边的子序列都小于或等于某个值，右边的子序列都大于等于某个值，左右子序列继续这种划分，直到整个序列有序为止。这是最原始的快速排序设计思想，它是分治算法的应用。

现在的问题是，拿什么作为基准把一个序列划分成两个子序列呢？弄不好一边只有一个元素，另一边则为其余所有元素，这种划分过程一直持续到排序完毕为止，这是最糟糕的情况，完全退化成了直接插入排序，复杂度为O(n2)。这个参考的基准，也就是序列里用于比较的某个特别的元素，就是支点，这个词来自力学。这样以来，选取支点就成了快速排序首当其冲要解决的问题。

选取支点常见的方案有三种，第一种情况是使用待排序序列的第一个元素或最后一个元素作为支点。采用这种方案的人非常乐观，以为最坏情况很难遇上。然而事情很多时候总是事与愿违，当一个待排序序列已经有序时就会遭遇最差情况。第二种方案是三点取中，以待排序序列中第一个元素，最中间那个元素和最后一个元素三者大小居中的那个作为支点，这就大大降低了遭遇最差情况的可能性，而且三点取中的代价很低。实际应用中，几乎所有版本的快速排序都采用了这种方案。第三种方案是随机选取支点，似乎这是最理想的情况，但是该方案一直搁浅。

显然，第一种选取支点的方案不值得我们去研究，我们先来尝试第二种选取支点的方案，稍后再尝试第三种方案。前面已经说过，当序列很短或基本有序时用直接插入排序比较快。我们可以考虑用直接插入排序来优化快速排序，否则当子序列少于三个元素时选取支点需要做特殊处理，再者，用递归来实现快速排序较为简单，而深层次递归的执行效率很低。

经过优化后三点取中快速排序过程示例如下：

27  98 96 96 40 79 91 86 29  85 56 72 45 85 60 12 14 92 97 26 89

三点取中

27  26  96 96 40 79 91 86 29 85 56 72 45 85 60 12 14 92 97 98 89

交换98和26

27  26  14 96 40 79 91 86 29 85 56 72 45 85 60 12 96 92 97 98 89

交换96和14

27  26  14 12 40 79 91 86 29 85 56 72 45 85 60 96 96 92 97 98 89

交换96和12

27  26  14 12 40 45 91 86 29 85 56 72 79 85 60 96 96 92 97 98 89

交换79和45

27  26  14 12 40 45 56 86 29 85 91 72 79 85 60 96 96 92 97 98 89

交换91和56

27  26  14 12 40 45 56 29 86 85 91 72 79 85 60 96 96 92 97 98 89

交换86和29

12  14  26 27 29 40 45 56 60 72 79 85 85 86 89 91 92 96 96 97 98

插入排序

原始的快速排序使用直接插入排序优化后，速度有了较大提升，但是最坏情况下退化成直接插入排序的诟病依然存在。解决这个问题需要用较低的代价获知排序过程中何时支点严重偏向一边，以便立即作出处理。这个难题被STL的另外一位大师David Musser在1997年解决，他使用监测递归深度的做法，当递归深度很大时说明支点严重偏斜，此时采用堆排序来保证O(nlogn)的时间复杂度。SGI STL里的sort采用了这种设计。

第三种选取支点的方案的原理非常简单，但是长期以来存在较大困难。首先，用软件产生随机数不是一件很容易的事，实际应用中只能用产生的伪随机数取代随机数，而伪随机数的质量和产生代价会影响快排的执行效率。这可能是长期以来一直没有人问津第三种选取支点方案的主要原因。再者，随机选取的支点未必十分适合需要排序的序列。在此，我们不做深入研究伪随机数的产生原理，以及随机选取的支点在多大程度上适合待排序的序列，因为二者均需要十分复杂的数学理论。


 1 // find the middle large entry in three
 2 template <typename T, typename Compare>
 3 inline const T& median(const T& a, const T& b, const T& c,
 4                        Compare cmp)
 5 {
 6   if(cmp(a, b))
 7     if(cmp(b, c))
 8       return b;
 9     else if(cmp(a, c))
10       return c;
11     else
12       return a;
13   else if(cmp(a, c))
14     return a;
15   else if(cmp(b, c))
16     return c;
17   else
18     return b;
19 }
20 
21 // split one sequence into two and return the partition address
22 template <typename RandomIterator, typename T, typename Compare>
23 RandomIterator unguarded_partition(RandomIterator first, RandomIterator last,
24                                    T pivot, Compare cmp)
25 {
26   for(; ;)
27   {
28     for(; cmp(*first, pivot); ++first);
29     for(--last; cmp(pivot, *last); --last);
30     if(!(first < last)) return first;
31       Sample::swap(*first, *last);
32     ++first;
33   }
34 }
35 
36 // the maximum depth of recursion if possible
37 inline int lg(int n)
38 {
39   int k;
40   for(k = 0; n > 1; n >>= 1) ++k;
41   return k;
42 }
43 
44 // an auxilary function for sort
45 template <typename RandomIterator, typename Compare>
46 void introsort_loop(RandomIterator first, RandomIterator last,
47                     int depth_limit,
48                     Compare cmp)
49 
50 {
51   while(last - first > 16)
52   {
53     if(0 == depth_limit)
54     {
55       partial_sort(first, last, last, cmp);
56       return;
57     }
58     --depth_limit;
59     RandomIterator cut = unguarded_partition(first, last,
60     median(*first, *(first + ((last - first) >> 1)),
61            *(last - 1), cmp),
62            cmp);
63     introsort_loop(cut, last, depth_limit, cmp);
64     last = cut;
65   }
66 }
67 
68 // quick sort -- SGI STL version
69 template <typename RandomIterator, typename Compare>
70 inline void sort(RandomIterator first, RandomIterator last, Compare cmp)
71 {
72   if(last - first > 16)
73     introsort_loop(first, last, lg(static_cast<int>(last - first)) << 1, cmp);
74  final_insertion_sort(first, last, cmp);
75 }
再来个支点随机选取的版本，随机数的产生，本主页有一些介绍，见
http://www.cppblog.com/Chipset/archive/2009/02/07/73177.html
 1 // the auxilary function of sort_r, the pivot is randomly chosen.
 2 template <typename RandomIterator, typename Compare>
 3 void introsort_loop_r(RandomIterator first, RandomIterator last, Compare cmp)
 4 {
 5   while(last - first > 16)
 6   {
 7     RandomIterator cut = unguarded_partition(first, last,
 8     *(first + rand32() % (last - first)), cmp); // rand32 comes from random.hpp
 9     introsort_loop_r(cut, last, cmp);
10     last = cut;
11   }
12 }
13 
14 // quick sort -- randomly pivot version
15 template <typename RandomIterator, typename Compare>
16 inline void sort_r(RandomIterator first, RandomIterator last, Compare cmp)
17 {
18   if(last - first > 16)
19     introsort_loop_r(first, last, cmp);
20   final_insertion_sort(first, last, cmp);
21 }
再来个最原始的版本，即使这个老掉牙的版本，也会比大多数教科书和baidu出来的大部分快排代码快一些，当然也包括C库函数qsort，后者慢的主要原因是比较函数不能内联，除非你拿出吃奶的力气用宏来做到内联:)
 1  // quick sort -- the most primitive version
 2 template <typename RandomIterator, typename Compare>
 3 inline void quick_sort(RandomIterator first, RandomIterator last, Compare cmp)
 4 {
 5   if(last - first > 1)
 6   {
 7     RandomIterator cut = unguarded_partition(first, last,
 8     median(*first, *(first + ((last - first) >> 1)), *(last - 1), cmp), cmp);
 9     quick_sort(first, cut, cmp);
10     quick_sort(cut, last, cmp);
11   }
12 }