我覺得在一般場合，單線程下快速排序是最快的，盡管它的時間復雜度為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://m.shnenglu.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 }