久久福利青草精品资源站免费 ,亚洲狠狠婷婷综合久久蜜芽,久久99精品久久只有精品

基本原理
   快速排序算法是一種分治排序算法，影響其性能的因素有劃分元素的選擇、小的子文件的處理、重復關鍵字等，本文論述針對重復關鍵字的改進實現。首先來回顧下一般的算法實現，其流程如下：
   a. 選擇一個劃分元素，這個元素在劃分后將在最終的位置上，通常是選擇最右端元素作為劃分點。
   b. 從左端開始掃描，直到找到大于劃分元素的元素；同時從右端開始掃描，直到找到小于劃分元素的元素，再交換使掃描停止的這兩個元素。
   c. 繼續步驟b，直到左指針不小于右指針，最后再交換左指針元素和劃分元素。
   d. 在左指針左側和右側區間(區間不包括左指針元素)重復以上過程，直至元素個數為0或1。
   在劃分的過程中，位于左指針左側的元素都比劃分元素小，右側的元素都比劃分元素大，如下圖所示

   由上述可見，一般的算法實現針對大量重復關鍵字的輸入情況，其性能表現很差，例如如果一個文件完全由相等的值(只有一個值)組成，那么它就不需要再進行任何排序，但前面的算法依然劃分直至得到小的子文件，無論文件有多大。針對這一情況，可以作實質性的改進，從而避免處理元素相同的子區間，提高效率。改進的算法實現主要問題在于如何處理與劃分元素相等的情況，這里的基本思想是將區間劃分為三個部分，左部分小于劃分元素，中間部分等于劃分元素，右部分大于劃分元素，然后再在左右兩部分進行子處理，具體的流程如下：
   a'. 選擇左端元素、中間元素和右端元素的中值作為劃分元素，也就是三者取中劃分，這樣能有效避免劃分區間的最壞情況。
   b'. 從左端開始掃描，直到找到不小于劃分元素的元素；同時從右端開始掃描，直到找到不大于劃分元素的元素，再交換使掃描停止的這兩個元素。如果左指針元素等于劃分元素，那么與左端的元素交換，并遞增左端位置(初始化為文件最左位置)；如果右指針元素等于劃分元素，那么與右端元素交換，并遞減右端位置(初始化為文件最右位置)。
   c'. 繼續步驟b'，直到左指針不小于右指針。
   d'. 交換最左端區間和左指針左側區間(不包括左指針元素)，這一過程會遞減左端位置；交換最右端區間和左指針右側區間(包括左指針元素)，這一過程會遞增右端位置。
   e'. 在最左端和最右端區間重復以上過程，直至元素個數為0或1。
   在劃分的過程中，與劃分元素相等的元素分布在最左端和最右端，如下圖所示

在劃分完成后處理子文件前，需要對調區間，如步驟d'所述，結果如下圖所示

代碼實現
上面所有圖中的v代表劃分元素，最后列出代碼清單，函數quick_sort有兩個版本，一個是支持operator < 的默認實現，另一個是支持帶謂詞的自定義比較實現。在其中用到了實現三者取中值的__median函數，對應的也有兩個版本實現，如下所示

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

_RandIt i = _first,j = _last-1,p = i,q = j,k;
8

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2));
9

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

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

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

quick_sort(_first,j+1);
29

quick_sort(i,_last);
30

}
31

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

_RandIt i = _first,j = _last-1,p = i, q = j, k;
39

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2),_comp);
40

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

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

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 春秋十二月閱讀(2704) | 評論 (1) | 編輯收藏

模板元編程（1）：選擇API

摘要: C與C++ API的比較在c語言中，API體現為c函數，如操作系統提供的一系列API，在c++中，API體現為自由函數，這里的自由函數是指除普通成員函數、靜態成員函數、友元函數外的能在某命名空間作用域或全局空間內直接訪問的函數，而這更多地體現為函數模板，如stl提供的一系列算法swap、count和sort等。相對于c API，c++ API具有類型安全和封... 閱讀全文

posted @ 2011-12-24 19:08 春秋十二月閱讀(2961) | 評論 (2) | 編輯收藏

真彩色靜態框CColorStatic類的設計實現

摘要: 關于cstatic控件的自繪，網上也有很多的代碼及文章，更有其界面畫得很漂亮的、多種多樣的功能。近來我自行封裝實現了一個真彩色靜態框類，目標初衷是從顏色、字體、光標入手，改變原始標準cstatic的色彩風格，使界面初步美化，具有好看的效果。同時作為一個基礎簡單的類來維護，為后續的功能增強及美化提供參考擴展，這個CColorStatic類的特點及功能如下：（1）文... 閱讀全文

posted @ 2011-12-18 00:54 春秋十二月閱讀(3754) | 評論 (1) | 編輯收藏

使用子類化截獲窗口消息

摘要: 在《多標簽視圖類CTabView的設計實現》一文中，CTabView從CBasicSubClassWnd私有繼承，重寫其虛函數SubWindowProc，捕獲WM_DRAWITEM和TTN_GETDISPINFO消息，從而實現了DrawItem和UpdateTooltipText虛函數回調機制，支持派生類的自定義處理，而CBasicSubClassWnd就是一個... 閱讀全文

posted @ 2011-12-11 11:07 春秋十二月閱讀(2301) | 評論 (0) | 編輯收藏

多標簽視圖類CTabView的設計實現

摘要: 在MFC9（在vc2008和vc2010中，已經有了CTabView的現成類）以前的版本中，有CListView,CTreeView,CEditView,CRichEditView等控件視圖類，但就是沒有類似的CTabView類，因工作需要，最近在做一個簡單的多標簽IE瀏覽器，開發環境是vs2005，基本框架是sdi + chtmlview + ctabview... 閱讀全文

posted @ 2011-12-11 00:47 春秋十二月閱讀(5205) | 評論 (3) | 編輯收藏

觀察者模式之應用: 系統托盤圖標類的設計

摘要: 關于系統托盤圖標類，網上也有很多的代碼，但都不太簡潔靈活易用，為了這一目的，本人自行封裝了一個API版本的實現類，這個類的設計思想來源于觀察者模式，從而較好地解耦了托盤通知消息的發送、接收、處理這三者間的關系，使這三者可以是同一個對象，也可以是不同的對象，具體的情況可根據業務邏輯靈活選擇控制，主要包括以下幾方面的特點：1）對于托盤通知消息的接收處理，提供了一個默... 閱讀全文

posted @ 2011-12-04 03:15 春秋十二月閱讀(1961) | 評論 (0) | 編輯收藏

使用正則表達式解析URL

   在開發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即可。

   為方便使用，封裝成了兩個自由模板函數，如下所示

template<typename charT>
2

inline 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

template<typename charT>
11

inline 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

}

測試示例如下

static const string protocol = "(?:(mailto|ssh|ftp|https?)://)?";
2

static 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]))";
3

static 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])";
4

static const string port = "(?::(\\d{1,5}))?";
5

static const string path = "(/.*)?";
6

static const string pattern = protocol + "((?:" + hostname + "|" + ip + "))" + port + path;
7

int _tmain(int argc, _TCHAR* argv[])
9

{
10

using namespace boost;
11

//形式1: 帶協議名,服務器為名稱,不帶端口號
13

bool ret;
14

string text = "http://www.shnenglu.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.shnenglu.com");
20

assert(what[3].str()=="");
21

assert(what[4].str()=="/qinqing1984");
22

//形式2: 不帶協議名,服務器為名稱,帶端口號
24

text = "www.shnenglu.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.shnenglu.com");
29

assert(what[3].str()=="80");
30

assert(what[4].str()=="/qinqing1984");
31

//形式3: 不帶協議名,服務器為名稱,不帶路徑
33

text = "www.shnenglu.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.shnenglu.com");
38

assert(what[3].str()=="80");
39

assert(what[4].str()=="");
40

//形式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

//形式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

//形式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

//形式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

//形式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

return 0;
71

}

對URL的解析，因時間有限，本文所述不盡詳細，只是略作分析，以點帶面，更多的精確匹配則依賴于實際的應用需求。

posted @ 2011-11-27 17:22 春秋十二月閱讀(7930) | 評論 (5) | 編輯收藏

基于stl序列容器實現的通用集合類 (線程安全版)

摘要: 在《基于stl序列容器實現的通用集合類》一文中，已經講到了具體實現，近來因再次用到它又改進完善了，主要體現在以下幾點：1）增加了查找操作方法，支持按值類型和謂詞條件兩種方式。2）增加重載了按值類型和謂詞條件2種方式刪除元素的方法。3）增加了2個模板參數以支持線程安全，一個是線程模型模板類，一個是互斥鎖類，使用loki庫來實現，因此所有方法現在都是線程安全的，當需... 閱讀全文

posted @ 2011-10-21 18:43 春秋十二月閱讀(3174) | 評論 (1) | 編輯收藏

基于雙端堆實現的優先級隊列（3）：外觀

摘要: 本文講述雙端堆的5個公開泛型操作算法：make_dheap（原位構造雙端堆）、push_dheap（插入元素）、pop_max_dheap（刪除最大元素）、pop_min_dheap（刪除最小元素），is_dheap（堆驗證），每個算法都提供<小于運算符和仿函數比較2個版本，要注意的是比較必須是嚴格弱序的，即對于<版本存在a<b為真且b<... 閱讀全文

posted @ 2011-10-05 13:24 春秋十二月閱讀(2627) | 評論 (1) | 編輯收藏

基于雙端堆實現的優先級隊列（2）：內幕

摘要: 在《基于雙端堆實現的優先級隊列（1）：原理》一文中講述了雙端堆的相關原理，本文則詳細講述具體的內部實現，便于區分，內部函數名稱都以雙下劃線作為前綴，在這里，有幾個關鍵問題需要說明 1）怎么求一個結點的對稱結點：如果完全二叉樹根結點從索引1開始但不存儲元素，那么最小堆根結點則在索引2，最大堆根結點則在索引3，4和5為2的左右孩... 閱讀全文

posted @ 2011-10-03 17:54 春秋十二月閱讀(2171) | 評論 (1) | 編輯收藏

僅列出標題

常用鏈接

留言簿(74)

隨筆分類(158)

隨筆檔案(159)

文章分類(30)

關注的開源項目

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜