随笔-88  评论-224  文章-23  trackbacks-0
基本原理
   快速排序算法是一种分治排序算法,影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等,本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现,其流程如下:
   a. 选择一个划分元素,这个元素在划分后将在最终的位置上,通常是选择最右端元素作为划分点。
   b. 从左端开始扫描,直到找到大于划分元素的元素;同时从右端开始扫描,直到找到小于划分元素的元素,再交换使扫描停止的这两个元素。
   c. 继续步骤b,直到左指针不小于右指针,最后再交换左指针元素和划分元素。
   d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程,直至元素个数为0或1。
   在划分的过程中,位于左指针左侧的元素都比划分元素小,右侧的元素都比划分元素大,如下图所示
   由上述可见,一般的算法实现针对大量重复关键字的输入情况,其性能表现很差,例如如果一个文件完全由相等的值(只有一个值)组成,那么它就不需要再进行任何排序,但前面的算法依然划分直至得到小的子文件,无论文件有多大。针对这一情况,可以作实质性的改进,从而避免处理元素相同的子区间,提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况,这里的基本思想是将区间划分为三个部分,左部分小于划分元素,中间部分等于划分元素,右部分大于划分元素,然后再在左右两部分进行子处理,具体的流程如下:
   a'. 选择左端元素、中间元素和右端元素的中值作为划分元素,也就是三者取中划分,这样能有效避免划分区间的最坏情况。
   b'. 从左端开始扫描,直到找到不小于划分元素的元素;同时从右端开始扫描,直到找到不大于划分元素的元素,再交换使扫描停止的这两个元素。如果左指针元素等于划分元素,那么与左端的元素交换,并递增左端位置(初始化为文件最左位置);如果右指针元素等于划分元素,那么与右端元素交换,并递减右端位置(初始化为文件最右位置)。
   c'. 继续步骤b',直到左指针不小于右指针。
   d'. 交换最左端区间和左指针左侧区间(不包括左指针元素),这一过程会递减左端位置;交换最右端区间和左指针右侧区间(包括左指针元素),这一过程会递增右端位置。
   e'. 在最左端和最右端区间重复以上过程,直至元素个数为0或1。
   在划分的过程中,与划分元素相等的元素分布在最左端和最右端,如下图所示
   在划分完成后处理子文件前,需要对调区间,如步骤d'所述,结果如下图所示

代码实现
   上面所有图中的v代表划分元素,最后列出代码清单,函数quick_sort有两个版本,一个是支持operator < 的默认实现,另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数,对应的也有两个版本实现,如下所示
 1template<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(*< pivot) ++i;
13        while(pivot < *j) --j;
14        if (!(i < j)) break;
15        std::iter_swap(i,j);
16        
17        if (!(*< pivot) && !(pivot < *i)) 
18            std::iter_swap(p++,i);
19        if (!(*< 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}
   从上面实现可看出,与一般的实现相比,划分过程多了两个if及for循环,if测试用来将找到的重复元素放在左右两端;for循环用来交换区间,将重复元素再放在中间,这额外的工作量只与找到的重复关键字的个数成线性,因此,即使在没有重复关键字的情况下,它也运行得很好,平均时间复杂度为O(NlgN)。
posted on 2012-05-19 14:48 春秋十二月 阅读(1647) 评论(1)  编辑 收藏 引用 所属分类: Algorithm

评论:
# re: 三路划分快速排序--针对重复关键字的改进 2015-09-12 19:55 | 御宅暴君
难得遇到用迭代器和模板的 C++ 实现(鼓掌  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理