快速排序算法是一種分治排序算法,影響其性能的因素有劃分元素的選擇、小的子文件的處理、重復關鍵字等,本文論述針對重復關鍵字的改進實現。首先來回顧下一般的算法實現,其流程如下:
a. 選擇一個劃分元素,這個元素在劃分后將在最終的位置上,通常是選擇最右端元素作為劃分點。
b. 從左端開始掃描,直到找到大于劃分元素的元素;同時從右端開始掃描,直到找到小于劃分元素的元素,再交換使掃描停止的這兩個元素。
c. 繼續步驟b,直到左指針不小于右指針,最后再交換左指針元素和劃分元素。
d. 在左指針左側和右側區間(區間不包括左指針元素)重復以上過程,直至元素個數為0或1。
在劃分的過程中,位于左指針左側的元素都比劃分元素小,右側的元素都比劃分元素大,如下圖所示
a'. 選擇左端元素、中間元素和右端元素的中值作為劃分元素,也就是三者取中劃分,這樣能有效避免劃分區間的最壞情況。
b'. 從左端開始掃描,直到找到不小于劃分元素的元素;同時從右端開始掃描,直到找到不大于劃分元素的元素,再交換使掃描停止的這兩個元素。如果左指針元素等于劃分元素,那么與左端的元素交換,并遞增左端位置(初始化為文件最左位置);如果右指針元素等于劃分元素,那么與右端元素交換,并遞減右端位置(初始化為文件最右位置)。
c'. 繼續步驟b',直到左指針不小于右指針。
d'. 交換最左端區間和左指針左側區間(不包括左指針元素),這一過程會遞減左端位置;交換最右端區間和左指針右側區間(包括左指針元素),這一過程會遞增右端位置。
e'. 在最左端和最右端區間重復以上過程,直至元素個數為0或1。
在劃分的過程中,與劃分元素相等的元素分布在最左端和最右端,如下圖所示
代碼實現
上面所有圖中的v代表劃分元素,最后列出代碼清單,函數quick_sort有兩個版本,一個是支持operator < 的默認實現,另一個是支持帶謂詞的自定義比較實現。在其中用到了實現三者取中值的__median函數,對應的也有兩個版本實現,如下所示
1
template<class _RandIt>
2
void 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
32
template<class _RandIt,class _Compare>
33
void 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
}
template<class _RandIt>2
void 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

32
template<class _RandIt,class _Compare>33
void 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
}



