我覺(jué)得在一般場(chǎng)合，單線程下快速排序是最快的，盡管它的時(shí)間復(fù)雜度為O(nlogn)，它甚至比時(shí)間復(fù)雜度為O(n)的基數(shù)排序、桶排序和計(jì)數(shù)排序都快一些。
如果對(duì)字符竄排序，即使快排的僅僅是字符竄的指針(避免拷貝字符竄)，burst sort還是比快速排序快一些。
快速排序的版本很多，常見(jiàn)的有C庫(kù)函數(shù)qsort，C++STL中的sort(多個(gè)版本)，還是大學(xué)書(shū)上的臃腫快速排序的實(shí)現(xiàn)。
這里介紹SGI STL版本的快速排序，它需要插入排序，堆排序和一般意義上的快速排序。

先看直接插入排序

直接插入排序的時(shí)間復(fù)雜度為O(n2)，最好情況下為O(n)，它的優(yōu)勢(shì)是當(dāng)序列很短或基本有序時(shí)排序速度比較快。此外，直接插入排序僅需要一個(gè)元素的額外存儲(chǔ)空間，空間復(fù)雜度為O(1)，很節(jié)約內(nèi)存。

假設(shè)有一個(gè)序列需要排序成升序，該序列含有n個(gè)元素，排序時(shí)從第i(i = 1, 2, …, n-1，注意C語(yǔ)言下標(biāo)從0開(kāi)始，因此存在第0個(gè)元素，在這點(diǎn)上，應(yīng)該順應(yīng)編程習(xí)慣，而不是通俗意義上的第1個(gè)，第2個(gè)…)個(gè)元素開(kāi)始跟它前面的元素逐個(gè)比較，直到比較到第j(j = 0, 1, …, i-1)個(gè)，如果該(第i個(gè))元素值比它前面的(第j個(gè))元素值小，但不比第j-1(j = 1, 2, …, i-1)個(gè)元素值小，則把該元素插入到第j個(gè)元素的前面(位于下標(biāo)區(qū)間[j, i)的所有元素需要事先后移一個(gè)元素位置)。

以一個(gè)隨機(jī)整數(shù)序列為例，插入排序的過(guò)程見(jiàn)下表。

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不動(dòng)

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

57不動(dòng)

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不動(dòng)

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不動(dòng)

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 }
再看堆排序

堆排序的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度O(1)，盡管平均速度比插入排序快得多，但在需要排序的一般場(chǎng)合，幾乎見(jiàn)不到它的應(yīng)用，因?yàn)楦焖倥判蚝头€(wěn)定排序比起來(lái)，它要顯著慢一些。問(wèn)題是，很多時(shí)候我們并不需要整個(gè)序列有序，僅僅需要從這個(gè)序列中找出一部分最大或最小的值。這種場(chǎng)合，堆排序十分擅長(zhǎng)。

原理如下，來(lái)自

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 }

快速排序的時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(logn)最壞情況下的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度O(n)。在C++標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)過(guò)程中，為了保證快速排序的速度，用堆排序?qū)焖倥判蜃隽藘?yōu)化，即使在最壞情況下，sort仍然可以維持O(nlogn)的時(shí)間復(fù)雜度，空間復(fù)雜度則不會(huì)超過(guò)O(logn)。在一般性應(yīng)用場(chǎng)合，快速排序不會(huì)愧對(duì)它的名字，盡管時(shí)間復(fù)雜度為O(nlogn)，但常數(shù)因子很小，因此排序速度比其它時(shí)間復(fù)雜度為O(nlogn)的堆排序和歸并排序要快一些，甚至超越了理論上比它快的基數(shù)排序和計(jì)數(shù)排序以及桶排序，這后三種排序的時(shí)間復(fù)雜度理論值可是O(n)哦。C++繼承了C庫(kù)，因此C庫(kù)里的qsort也被繼承下來(lái)，只不過(guò)sort要比qsort排序速度快得多。

對(duì)于一個(gè)無(wú)需序列而言，當(dāng)我們需要把它變成一個(gè)升序序列時(shí)，可以把它一分為二，使左邊的子序列都小于或等于某個(gè)值，右邊的子序列都大于等于某個(gè)值，左右子序列繼續(xù)這種劃分，直到整個(gè)序列有序?yàn)橹埂＿@是最原始的快速排序設(shè)計(jì)思想，它是分治算法的應(yīng)用。

現(xiàn)在的問(wèn)題是，拿什么作為基準(zhǔn)把一個(gè)序列劃分成兩個(gè)子序列呢？弄不好一邊只有一個(gè)元素，另一邊則為其余所有元素，這種劃分過(guò)程一直持續(xù)到排序完畢為止，這是最糟糕的情況，完全退化成了直接插入排序，復(fù)雜度為O(n2)。這個(gè)參考的基準(zhǔn)，也就是序列里用于比較的某個(gè)特別的元素，就是支點(diǎn)，這個(gè)詞來(lái)自力學(xué)。這樣以來(lái)，選取支點(diǎn)就成了快速排序首當(dāng)其沖要解決的問(wèn)題。

選取支點(diǎn)常見(jiàn)的方案有三種，第一種情況是使用待排序序列的第一個(gè)元素或最后一個(gè)元素作為支點(diǎn)。采用這種方案的人非常樂(lè)觀，以為最壞情況很難遇上。然而事情很多時(shí)候總是事與愿違，當(dāng)一個(gè)待排序序列已經(jīng)有序時(shí)就會(huì)遭遇最差情況。第二種方案是三點(diǎn)取中，以待排序序列中第一個(gè)元素，最中間那個(gè)元素和最后一個(gè)元素三者大小居中的那個(gè)作為支點(diǎn)，這就大大降低了遭遇最差情況的可能性，而且三點(diǎn)取中的代價(jià)很低。實(shí)際應(yīng)用中，幾乎所有版本的快速排序都采用了這種方案。第三種方案是隨機(jī)選取支點(diǎn)，似乎這是最理想的情況，但是該方案一直擱淺。

顯然，第一種選取支點(diǎn)的方案不值得我們?nèi)パ芯浚覀兿葋?lái)嘗試第二種選取支點(diǎn)的方案，稍后再?lài)L試第三種方案。前面已經(jīng)說(shuō)過(guò)，當(dāng)序列很短或基本有序時(shí)用直接插入排序比較快。我們可以考慮用直接插入排序來(lái)優(yōu)化快速排序，否則當(dāng)子序列少于三個(gè)元素時(shí)選取支點(diǎn)需要做特殊處理，再者，用遞歸來(lái)實(shí)現(xiàn)快速排序較為簡(jiǎn)單，而深層次遞歸的執(zhí)行效率很低。

經(jīng)過(guò)優(yōu)化后三點(diǎn)取中快速排序過(guò)程示例如下：

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

三點(diǎn)取中

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

插入排序

原始的快速排序使用直接插入排序優(yōu)化后，速度有了較大提升，但是最壞情況下退化成直接插入排序的詬病依然存在。解決這個(gè)問(wèn)題需要用較低的代價(jià)獲知排序過(guò)程中何時(shí)支點(diǎn)嚴(yán)重偏向一邊，以便立即作出處理。這個(gè)難題被STL的另外一位大師David Musser在1997年解決，他使用監(jiān)測(cè)遞歸深度的做法，當(dāng)遞歸深度很大時(shí)說(shuō)明支點(diǎn)嚴(yán)重偏斜，此時(shí)采用堆排序來(lái)保證O(nlogn)的時(shí)間復(fù)雜度。SGI STL里的sort采用了這種設(shè)計(jì)。

第三種選取支點(diǎn)的方案的原理非常簡(jiǎn)單，但是長(zhǎng)期以來(lái)存在較大困難。首先，用軟件產(chǎn)生隨機(jī)數(shù)不是一件很容易的事，實(shí)際應(yīng)用中只能用產(chǎn)生的偽隨機(jī)數(shù)取代隨機(jī)數(shù)，而偽隨機(jī)數(shù)的質(zhì)量和產(chǎn)生代價(jià)會(huì)影響快排的執(zhí)行效率。這可能是長(zhǎng)期以來(lái)一直沒(méi)有人問(wèn)津第三種選取支點(diǎn)方案的主要原因。再者，隨機(jī)選取的支點(diǎn)未必十分適合需要排序的序列。在此，我們不做深入研究偽隨機(jī)數(shù)的產(chǎn)生原理，以及隨機(jī)選取的支點(diǎn)在多大程度上適合待排序的序列，因?yàn)槎呔枰謴?fù)雜的數(shù)學(xué)理論。


 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 }
再來(lái)個(gè)支點(diǎn)隨機(jī)選取的版本，隨機(jī)數(shù)的產(chǎn)生，本主頁(yè)有一些介紹，見(jiàn)
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 }
再來(lái)個(gè)最原始的版本，即使這個(gè)老掉牙的版本，也會(huì)比大多數(shù)教科書(shū)和baidu出來(lái)的大部分快排代碼快一些，當(dāng)然也包括C庫(kù)函數(shù)qsort，后者慢的主要原因是比較函數(shù)不能內(nèi)聯(lián)，除非你拿出吃奶的力氣用宏來(lái)做到內(nèi)聯(lián):)
 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 }