基本原理 快速排序算法是一種分治排序算法，影響其性能的因素有劃分元素的選擇、小的子文件的處理、重復(fù)關(guān)鍵字等，本文論述針對(duì)重復(fù)關(guān)鍵字的改進(jìn)實(shí)現(xiàn)。首先來(lái)回顧下一般的算法實(shí)現(xiàn)，其流程如下：
a. 選擇一個(gè)劃分元素，這個(gè)元素在劃分后將在最終的位置上，通常是選擇
最右端元素作為劃分點(diǎn)。
b. 從左端開(kāi)始掃描，直到找到
大于劃分元素的元素；同時(shí)從右端開(kāi)始掃描，直到找到
小于劃分元素的元素，再交換使掃描停止的這兩個(gè)元素。
c. 繼續(xù)步驟b，直到左指針不小于右指針，最后再交換左指針元素和劃分元素。
d. 在左指針左側(cè)和右側(cè)區(qū)間(區(qū)間不包括左指針元素)重復(fù)以上過(guò)程，直至元素個(gè)數(shù)為0或1。
在劃分的過(guò)程中，位于左指針左側(cè)的元素都比劃分元素小，右側(cè)的元素都比劃分元素大，如下圖所示
由上述可見(jiàn)，一般的算法實(shí)現(xiàn)針對(duì)大量重復(fù)關(guān)鍵字的輸入情況，其性能表現(xiàn)很差，例如如果一個(gè)文件完全由相等的值(只有一個(gè)值)組成，那么它就不需要再進(jìn)行任何排序，但前面的算法依然劃分直至得到小的子文件，無(wú)論文件有多大。針對(duì)這一情況，可以作實(shí)質(zhì)性的改進(jìn)，從而避免處理元素相同的子區(qū)間，提高效率。改進(jìn)的算法實(shí)現(xiàn)主要問(wèn)題在于如何處理與劃分元素相等的情況，這里的基本思想是將區(qū)間劃分為三個(gè)部分，左部分小于劃分元素，中間部分等于劃分元素，右部分大于劃分元素，然后再在左右兩部分進(jìn)行子處理，具體的流程如下：
a'. 選擇左端元素、中間元素和右端元素的中值作為劃分元素，也就是
三者取中劃分，這樣能有效避免劃分區(qū)間的最壞情況。
b'. 從左端開(kāi)始掃描，直到找到
不小于劃分元素的元素；同時(shí)從右端開(kāi)始掃描，直到找到
不大于劃分元素的元素，再交換使掃描停止的這兩個(gè)元素。如果左指針元素等于劃分元素，那么與左端的元素交換，并遞增左端位置(初始化為文件最左位置)；如果右指針元素等于劃分元素，那么與右端元素交換，并遞減右端位置(初始化為文件最右位置)。
c'. 繼續(xù)步驟b'，直到左指針不小于右指針。
d'. 交換最左端區(qū)間和左指針左側(cè)區(qū)間(不包括左指針元素)，這一過(guò)程會(huì)遞減左端位置；交換最右端區(qū)間和左指針右側(cè)區(qū)間(包括左指針元素)，這一過(guò)程會(huì)遞增右端位置。
e'. 在最左端和最右端區(qū)間重復(fù)以上過(guò)程，直至元素個(gè)數(shù)為0或1。
在劃分的過(guò)程中，與劃分元素相等的元素分布在最左端和最右端，如下圖所示
在劃分完成后處理子文件前，需要對(duì)調(diào)區(qū)間，如步驟d'所述，結(jié)果如下圖所示
代碼實(shí)現(xiàn) 上面所有圖中的v代表劃分元素，最后列出代碼清單，函數(shù)quick_sort有兩個(gè)版本，一個(gè)是支持operator < 的默認(rèn)實(shí)現(xiàn)，另一個(gè)是支持帶謂詞的自定義比較實(shí)現(xiàn)。在其中用到了實(shí)現(xiàn)三者取中值的__median函數(shù)，對(duì)應(yīng)的也有兩個(gè)版本實(shí)現(xiàn)，如下所示
1
template<class _RandIt>
2void quick_sort(_RandIt _first,_RandIt _last)
3
{
4
typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
5 if (!(_first<_last-1)) return;
6
7 _RandIt i = _first,j = _last-1,p = i,q = j,k;
8 _ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2));
9
10 while(true)
11
{
12 while(*i < pivot) ++i;
13 while(pivot < *j) --j;
14 if (!(i < j)) break;
15 std::iter_swap(i,j);
16
17 if (!(*i < pivot) && !(pivot < *i))
18 std::iter_swap(p++,i);
19 if (!(*j < pivot) && !(pivot < *j))
20 std::iter_swap(q--,j);
21 ++i; --j;
22
}
23
24 j = i - 1;
25 for(k = _first;k<p;--j,++k) std::iter_swap(k,j);
26 for(k = _last-1;k>q;++i,--k) std::iter_swap(k,i);
27
28 quick_sort(_first,j+1);
29 quick_sort(i,_last);
30
}
31
32template<class _RandIt,class _Compare>
33void quick_sort(_RandIt _first,_RandIt _last,_Compare _comp)
34{
35 typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
36 if (!(_first < _last - 1)) return;
37
38 _RandIt i = _first,j = _last-1,p = i, q = j, k;
39 _ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2),_comp);
40
41 while(true)
42 {
43 while(_comp(*i,pivot)) ++i;
44 while(_comp(pivot,*j)) --j;
45 if (!(i < j)) break;
46 std::iter_swap(i,j);
47
48 if (!_comp(*i,pivot) && !_comp(pivot,*i))
49 std::iter_swap(p++,i);
50 if (!_comp(*j,pivot) && !_comp(pivot,*j))
51 std::iter_swap(q--,j);
52 ++i; --j;
53 }
54 j = i - 1;
55 for(k = _first;k < p;++k,--j)
56 std::iter_swap(k,j);
57 for(k = _last - 1;k > q;--k,++i)
58 std::iter_swap(k,i);
59
60 quick_sort(_first,j+1,_comp);
61 quick_sort(i,_last,_comp);
62} 從上面實(shí)現(xiàn)可看出，與一般的實(shí)現(xiàn)相比，劃分過(guò)程多了兩個(gè)if及for循環(huán)，if測(cè)試用來(lái)將找到的重復(fù)元素放在左右兩端；for循環(huán)用來(lái)交換區(qū)間，將重復(fù)元素再放在中間，這額外的工作量只與找到的重復(fù)關(guān)鍵字的個(gè)數(shù)成線性，因此，即使在沒(méi)有重復(fù)關(guān)鍵字的情況下，它也運(yùn)行得很好，平均時(shí)間復(fù)雜度為O(NlgN)。
posted on 2012-05-19 14:48
春秋十二月 閱讀(2703)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
Algorithm