基本原理 快速排序算法是一种分治排序算法，影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等，本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现，其流程如下：
a. 选择一个划分元素，这个元素在划分后将在最终的位置上，通常是选择
最右端元素作为划分点。
b. 从左端开始扫描，直到找到
大于划分元素的元素；同时从右端开始扫描，直到找到
小于划分元素的元素，再交换使扫描停止的这两个元素。
c. 继续步骤b，直到左指针不小于右指针，最后再交换左指针元素和划分元素。
d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程，直至元素个数为0或1。
在划分的过程中，位于左指针左侧的元素都比划分元素小，右侧的元素都比划分元素大，如下图所示
由上述可见，一般的算法实现针对大量重复关键字的输入情况，其性能表现很差，例如如果一个文件完全由相等的值(只有一个值)组成，那么它就不需要再进行任何排序，但前面的算法依然划分直至得到小的子文件，无论文件有多大。针对这一情况，可以作实质性的改进，从而避免处理元素相同的子区间，提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况，这里的基本思想是将区间划分为三个部分，左部分小于划分元素，中间部分等于划分元素，右部分大于划分元素，然后再在左右两部分进行子处理，具体的流程如下：
a'. 选择左端元素、中间元素和右端元素的中值作为划分元素，也就是
三者取中划分，这样能有效避免划分区间的最坏情况。
b'. 从左端开始扫描，直到找到
不小于划分元素的元素；同时从右端开始扫描，直到找到
不大于划分元素的元素，再交换使扫描停止的这两个元素。如果左指针元素等于划分元素，那么与左端的元素交换，并递增左端位置(初始化为文件最左位置)；如果右指针元素等于划分元素，那么与右端元素交换，并递减右端位置(初始化为文件最右位置)。
c'. 继续步骤b'，直到左指针不小于右指针。
d'. 交换最左端区间和左指针左侧区间(不包括左指针元素)，这一过程会递减左端位置；交换最右端区间和左指针右侧区间(包括左指针元素)，这一过程会递增右端位置。
e'. 在最左端和最右端区间重复以上过程，直至元素个数为0或1。
在划分的过程中，与划分元素相等的元素分布在最左端和最右端，如下图所示
在划分完成后处理子文件前，需要对调区间，如步骤d'所述，结果如下图所示
代码实现 上面所有图中的v代表划分元素，最后列出代码清单，函数quick_sort有两个版本，一个是支持operator < 的默认实现，另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数，对应的也有两个版本实现，如下所示
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} 从上面实现可看出，与一般的实现相比，划分过程多了两个if及for循环，if测试用来将找到的重复元素放在左右两端；for循环用来交换区间，将重复元素再放在中间，这额外的工作量只与找到的重复关键字的个数成线性，因此，即使在没有重复关键字的情况下，它也运行得很好，平均时间复杂度为O(NlgN)。
posted @
2012-05-19 14:48 春秋十二月 阅读(2701) |
评论 (1) |
编辑 收藏
摘要: C与C++ API的比较
在c语言中，API体现为c函数，如操作系统提供的一系列API，在c++中，API体现为自由函数，这里的自由函数是指除普通成员函数、静态成员函数、友元函数外的能在某命名空间作用域或全局空间内直接访问的函数，而这更多地体现为函数模板，如stl提供的一系列算法swap、count和sort等。相对于c API，c++ API具有类型安全和封...
阅读全文
posted @
2011-12-24 19:08 春秋十二月 阅读(2959) |
评论 (2) |
编辑 收藏
摘要: 关于cstatic控件的自绘，网上也有很多的代码及文章，更有其界面画得很漂亮的、多种多样的功能。近来我自行封装实现了一个真彩色静态框类，目标初衷是从颜色、字体、光标入手，改变原始标准cstatic的色彩风格，使界面初步美化，具有好看的效果。同时作为一个基础简单的类来维护，为后续的功能增强及美化提供参考扩展，这个CColorStatic类的特点及功能如下：（1）文...
阅读全文
posted @
2011-12-18 00:54 春秋十二月 阅读(3752) |
评论 (1) |
编辑 收藏
摘要: 在《多标签视图类CTabView的设计实现》一文中，CTabView从CBasicSubClassWnd私有继承，重写其虚函数SubWindowProc，捕获WM_DRAWITEM和TTN_GETDISPINFO消息，从而实现了DrawItem和UpdateTooltipText虚函数回调机制，支持派生类的自定义处理，而CBasicSubClassWnd就是一个...
阅读全文
posted @
2011-12-11 11:07 春秋十二月 阅读(2299) |
评论 (0) |
编辑 收藏
摘要: 在MFC9（在vc2008和vc2010中，已经有了CTabView的现成类）以前的版本中，有CListView,CTreeView,CEditView,CRichEditView等控件视图类，但就是没有类似的CTabView类，因工作需要，最近在做一个简单的多标签IE浏览器，开发环境是vs2005，基本框架是sdi + chtmlview + ctabview...
阅读全文
posted @
2011-12-11 00:47 春秋十二月 阅读(5200) |
评论 (3) |
编辑 收藏
摘要: 关于系统托盘图标类，网上也有很多的代码，但都不太简洁灵活易用，为了这一目的，本人自行封装了一个API版本的实现类，这个类的设计思想来源于观察者模式，从而较好地解耦了托盘通知消息的发送、接收、处理这三者间的关系，使这三者可以是同一个对象，也可以是不同的对象，具体的情况可根据业务逻辑灵活选择控制，主要包括以下几方面的特点：1）对于托盘通知消息的接收处理，提供了一个默...
阅读全文
posted @
2011-12-04 03:15 春秋十二月 阅读(1958) |
评论 (0) |
编辑 收藏
在开发HTTP相关程序时，经常会碰到从网络链接URL中提取协议名、服务器、路径等目标对象，如果使用C/C++字符串操作函数，那么则显得有点麻烦且代码不易维护，其实关于文本内容的解析工作，都可优先考虑使用正则表达式库来解决处理，C++方面的正则库也有很多种，如atl、pcre、boost。下面就使用boost中的regex来解析URL提取协议名、服务器、路径为目标说明其用法。
协议名 可有可无，如果有时则后面必跟着://，如果没有，则默认为使用http协议。通常还有其它的协议如https、ssl、ftp、mailto等。因此匹配协议名的正则表达式应该是(?:(mailto|ssh|ftp|https?)://)?，注意这个表达式本身捕获了协议名，但不包括://。
服务器 或是域名，如www.csdn.net；或是IP地址，如192.168.1.1，可带端口号，如192.168.1.1:8080。匹配域名的正则表达式为(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))，表达式"(?:com|net|edu|biz|gov|org|in(?:t|fo)"匹配了com、net、edu、biz、gov、org、int、info等常见的域名，而(?-i:[a-z][a-z])匹配了国家代码，而且只允许小写为合法的，如www.richcomm.com.cn。匹配IP要尽量精确，考虑到IP每部分应为数字且范围在0-255之间，因此表达式应为(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])。注意以上域名或IP的正则式本身不捕获它们，这是为了留在后面作为整体捕获。
端口号的正则表达式为(?::(\d{1,5}))?，这里限制了端口号为1至5位的数字，更精确的匹配如要求在某范围如[1024,65535]间则可参考以上IP正则模式。综上所得，匹配服务器的正则表达式为((?:(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))|(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])\.(?:[01]?\d\d?|2[0-4]\d|25[0-5])))(?::(\d{1,5}))?，这个正则式作为整体捕获了域名或IP，及端口号（若有），如www.csdn.net，则得到www.csdn.net和空（没有端口，http默认为80，https默认为443）子串；192.168.1.1:8080则得到192.168.1.1和8080子串。
路径 最简单的形式为(/.*)?，更精确的形式为/[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]*(?:[.!,?]+[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]+)*。
以上所有正则表达式均为ascii字符集，对于unicode字符集则在其前加L即可。
为方便使用，封装成了两个自由模板函数，如下所示
1template<typename charT>
2inline bool boost_match(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
3{
4 boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags);
5 if(NULL==result)
6 return boost::regex_match(text,expression);
7 return boost::regex_match(text,*result,expression);
8}
9
10template<typename charT>
11inline bool boost_search(const charT* pattern,const charT* text,unsigned int flags=boost::regex::normal,boost::match_results<const charT*>* result=NULL)
12{
13 boost::basic_regex<charT,boost::regex_traits<charT> > expression(pattern,flags);
14 if(NULL==result)
15 return boost::regex_search(text,expression);
16 return boost::regex_search(text,*result,expression);
17}
测试示例如下
1
static const string protocol = "(?:(mailto|ssh|ftp|https?)://)?";
2static const string hostname = "(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\\.)+(?:com|net|edu|biz|gov|org|in(?:t|fo)|(?-i:[a-z][a-z]))";
3static const string ip = "(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])\\.(?:[01]?\\d\\d?|2[0-4]\\d|25[0-5])";
4static const string port = "(?::(\\d{1,5}))?";
5static const string path = "(/.*)?";
6static const string pattern = protocol + "((?:" + hostname + "|" + ip + "))" + port + path;
7
8int _tmain(int argc, _TCHAR* argv[])
9
{
10
using namespace boost;
11
12 //形式1: 带协议名,服务器为名称,不带端口号
13 bool ret;
14 string text = "http://www.cppblog.com/qinqing1984";
15 boost::cmatch what;
16 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
17 assert(ret);
18 assert(what[1].str()=="http");
19 assert(what[2].str()=="www.cppblog.com");
20 assert(what[3].str()=="");
21 assert(what[4].str()=="/qinqing1984");
22
23 //形式2: 不带协议名,服务器为名称,带端口号
24 text = "www.cppblog.com:80/qinqing1984";
25 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
26 assert(ret);
27 assert(what[1].str()=="");
28 assert(what[2].str()=="www.cppblog.com");
29 assert(what[3].str()=="80");
30 assert(what[4].str()=="/qinqing1984");
31
32 //形式3: 不带协议名,服务器为名称,不带路径
33 text = "www.cppblog.com:80";
34 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
35 assert(ret);
36 assert(what[1].str()=="");
37 assert(what[2].str()=="www.cppblog.com");
38 assert(what[3].str()=="80");
39 assert(what[4].str()=="");
40
41 //形式4: 协议为https,服务器为IP,带端口号
42 text = "https://192.168.1.1:443/index.html";
43 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
44 assert(ret);
45 assert(what[1].str()=="https");
46 assert(what[2].str()=="192.168.1.1");
47 assert(what[3].str()=="443");
48 assert(what[4].str()=="/index.html");
49
50 //形式5: 端口超过5位数
51 text = "ftp://192.168.1.1:888888";
52 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
53 assert(!ret);
54
55 //形式6: 没有协议名
56 text = "//192.168.1.1/index.html";
57 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
58 assert(!ret);
59
60 //形式7: 没有服务器
61 text = "http:///index.html";
62 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
63 assert(!ret);
64
65 //形式8: 不合法的服务器
66 text = "cppblog/index.html";
67 ret=boost_match(pattern.c_str(),text.c_str(),regex::icase|regex::perl,&what);
68 assert(!ret);
69
70 return 0;
71
}
对URL的解析，因时间有限，本文所述不尽详细，只是略作分析，以点带面，更多的精确匹配则依赖于实际的应用需求。
posted @
2011-11-27 17:22 春秋十二月 阅读(7926) |
评论 (5) |
编辑 收藏
摘要: 在《基于stl序列容器实现的通用集合类》一文中，已经讲到了具体实现，近来因再次用到它又改进完善了，主要体现在以下几点：1）增加了查找操作方法，支持按值类型和谓词条件两种方式。2）增加重载了按值类型和谓词条件2种方式删除元素的方法。3）增加了2个模板参数以支持线程安全，一个是线程模型模板类，一个是互斥锁类，使用loki库来实现，因此所有方法现在都是线程安全的，当需...
阅读全文
posted @
2011-10-21 18:43 春秋十二月 阅读(3170) |
评论 (1) |
编辑 收藏
摘要: 本文讲述双端堆的5个公开泛型操作算法：make_dheap（原位构造双端堆）、push_dheap（插入元素）、pop_max_dheap（删除最大元素）、pop_min_dheap（删除最小元素），is_dheap（堆验证），每个算法都提供<小于运算符和仿函数比较2个版本，要注意的是比较必须是严格弱序的，即对于<版本存在a<b为真且b<...
阅读全文
posted @
2011-10-05 13:24 春秋十二月 阅读(2624) |
评论 (1) |
编辑 收藏
摘要: 在《基于双端堆实现的优先级队列（1）：原理》一文中讲述了双端堆的相关原理，本文则详细讲述具体的内部实现，便于区分，内部函数名称都以双下划线作为前缀，在这里，有几个关键问题需要说明
1）怎么求一个结点的对称结点：如果完全二叉树根结点从索引1开始但不存储元素，那么最小堆根结点则在索引2，最大堆根结点则在索引3，4和5为2的左右孩...
阅读全文
posted @
2011-10-03 17:54 春秋十二月 阅读(2170) |
评论 (1) |
编辑 收藏