青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

liyuxia713

蹣跚前行者

常用鏈接

統(tǒng)計(jì)

Algorithms

C++

最新評(píng)論

基本排序算法及分析(四):快速排序

快速排序:
 1/*----------------------------------------------------------------------------------------------
 2Quick_sort.h
 3快速排序:確定一個(gè)樞紐元,一次遍歷后將數(shù)組劃分成兩個(gè)部分,第一部分均比樞紐元小
 4         第二部分都比樞紐元大,然后對(duì)這兩個(gè)數(shù)組進(jìn)行快速排序,是一種遞歸的方法
 5平均運(yùn)行時(shí)間O(Nlog(N)),最壞運(yùn)行時(shí)間O(N^2)
 6最壞情形:對(duì)于預(yù)排序的序列。
 7對(duì)與樞紐元相等的元素處理:
 8    i,j都停止:會(huì)比較相等元素,但是可以劃分成長(zhǎng)度相當(dāng)?shù)膬蓚€(gè)子數(shù)組
 9    i,j都不停止,不會(huì)比較相等元素,但是可能產(chǎn)生長(zhǎng)度不平衡的兩個(gè)子數(shù)組(與樞紐元相等的元素較多時(shí))
10樞紐元的選取:
111. 選取第一個(gè)元素做樞紐元:對(duì)于(部分)預(yù)排序的序列運(yùn)行時(shí)間O(N^2)
122. 隨機(jī)生成樞紐元:能避免上述問題,但是產(chǎn)生樞紐元的代價(jià)高
133. 三數(shù)中值分割法:選取左端,右端,中間位置三個(gè)元素的中值
14----------------------------------------------------------------------------------------------*/

15#ifndef QUICK_SORT_H
16#define QUICK_SORT_H
17
18#include "typedef.h" /* typedef int T 待排序的元素類型只要在這個(gè)文件中控制即可. */
19#include "swap.h" /*交換兩個(gè)元素值*/
20
21/* 選取第一個(gè)元素做樞紐元的情形----返回樞紐元位置*/
22int Quick_sort_divide(T*a, int begin, int end)
23{
24    T key = a[begin];
25
26    while(begin < end)
27    {
28        while(begin < end && a[end] >= key) --end;
29            a[begin] = a[end]; //不能--end,下面循環(huán)還要給現(xiàn)在的end位置賦值呢!         
30            //swap(a[begin],a[end]);
31        while(begin < end && a[begin] <= key) ++begin;
32            a[end] = a[begin];
33            //swap(a[begin],a[end]);
34    }

35    a[begin] = key;
36    
37    return begin;
38}

39
40/*三數(shù)中值割分法----選取樞紐元*/
41const int& median3(T*a, int begin, int end)
42{
43    int mid = (begin + end)/2;
44    //將三個(gè)位置的元素,按順序擺好,一會(huì)兒begin,end位置的元素就無(wú)需參加比較
45    if(a[mid] < a[begin]) swap(a[mid],a[begin]);
46    if(a[end] < a[begin]) swap(a[end],a[begin]);
47    if(a[mid] > a[end]) swap(a[mid],a[end]);
48    
49    swap(a[mid],a[end-1]); //將樞紐元放到倒數(shù)第二個(gè)位置
50    return a[end-1];
51}

52
53
54/*三數(shù)中值分割法----分割:返回樞紐元位置*/
55int Quick_sort_divide_3v(T*a, int begin,int end)
56{
57    T key = median3(a,begin,end);
58    int tag = end - 1;
59    begin = begin + 1//選取樞紐元時(shí)原begin位置的元素已設(shè)置成小于key的
60    end = end - 2//原end位置值已設(shè)置成大于key的,end-1位置為key,都不用考慮
61    while(begin < end)
62    {
63        while(a[begin] < key) ++begin;
64        while(a[end] > key) --end;
65        if(begin < end) swap(a[begin],a[end]);
66    }

67    swap(a[begin],a[tag]);
68    return begin;
69}

70
71/*一次分割*/
72void Quick_sort_step(T*a, int begin, int end)
73{    
74    if(begin < end)
75    {
76        int k = Quick_sort_divide_3v(a,begin,end); //三數(shù)中值割分法
77        //int k = Quick_sort_divide(a,begin,end); //選第一個(gè)元素做樞紐元
78        Quick_sort_step(a,begin,k-1);
79        Quick_sort_step(a,k+1,end);
80    }

81}

82/*快速排序*/
83void Quick_sort(T* a, int n)
84{
85    //if(n > 10) 當(dāng)元素個(gè)數(shù)少時(shí)不必用快速插入法    
86        Quick_sort_step(a,0,n-1);
87    //else Insertion_sort(a,n);
88}

89
90#endif

 
  

posted on 2009-04-22 16:56 幸運(yùn)草 閱讀(2899) 評(píng)論(8)  編輯 收藏 引用 所屬分類: Algorithms

評(píng)論

# re: 基本排序算法及分析(四):快速排序 2009-04-28 21:27 shongbee2

哈哈,終于弄清楚了。謝謝您。。以后多交流哈。呵呵  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2009-10-10 15:30 Linsea

我想問下那個(gè)logN對(duì)數(shù)都沒有底數(shù),那個(gè)底數(shù)是多少?2嗎?
我看嚴(yán)蔚敏的書上有的地方有底數(shù)2,有的地方?jīng)]有,是怎么回事,這個(gè)問題困擾我好久了,望博主對(duì)回答,謝謝!  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2009-10-17 10:19 幸運(yùn)草

@Linsea
是以2為底的logN,我想有的時(shí)候沒寫是默認(rèn)是2吧,因?yàn)槎鏄湟话闵婕暗亩际且?為底的指數(shù)函數(shù),反過來(lái)也是以2為底的對(duì)數(shù)函數(shù)。

具體的解釋我放在原日志最下端了,因?yàn)槲抑荒芤詧D片的格式插入數(shù)學(xué)公式,所以就沒有辦法放在回復(fù)里了,你看一下,有問題再聯(lián)系我  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2012-06-28 00:58 我是大熊

最近也在看快排,希望一起討論
http://php.oil58.com/  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2012-06-28 11:31 liyuxia713

@我是大熊

去貴頁(yè)面瀏覽了下,文筆風(fēng)格比較吸引人,但頁(yè)面排版看著有些亂  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2012-07-04 03:15 我是大熊

@liyuxia713
謝謝!!可能是瀏覽器兼容性的關(guān)系!不過在改進(jìn)了!
  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2012-07-04 03:39 我是大熊

我寫的快排,簡(jiǎn)單的理解,沒你的這么深。可以的話,幫我看看!
http://php.oil58.com/?p=206  回復(fù)  更多評(píng)論   

# re: 基本排序算法及分析(四):快速排序 2012-07-04 03:41 我是大熊

不支持這個(gè)鏈接,不好意思
http://php.oil58.com/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-c/  回復(fù)  更多評(píng)論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲一区视频在线| 久久一区精品| 欧美一级成年大片在线观看| 国产精品一区二区视频| 欧美肥婆在线| 伊人久久婷婷| 国产精品私拍pans大尺度在线| 欧美一级播放| 一级日韩一区在线观看| 国产精品久久网| 久久国产成人| 欧美欧美在线| 久久色在线观看| 欧美一区二区三区日韩视频| 亚洲色在线视频| 亚洲欧美日韩综合| 亚洲欧美日韩精品在线| 宅男精品视频| 欧美韩日一区二区| 久久一综合视频| 免费日韩视频| 美女福利精品视频| 中文国产一区| 欧美电影免费观看大全| 美女网站久久| 亚洲狼人综合| 宅男精品视频| 欧美日韩在线精品| 国产精品一区二区在线观看不卡| 国产精品日韩欧美大师| 国产欧美日韩在线视频| 国产美女精品视频免费观看| 国产精品丝袜白浆摸在线| 国产视频亚洲| 亚洲黄色成人| 欧美与黑人午夜性猛交久久久| 亚洲欧美日韩天堂一区二区| 亚洲福利专区| av成人免费在线| 亚洲欧洲精品成人久久奇米网| 一本色道久久综合亚洲精品按摩 | 99精品视频免费在线观看| 中文av一区二区| 欧美国产亚洲精品久久久8v| 精品va天堂亚洲国产| 久久精品道一区二区三区| 亚洲永久免费精品| 欧美成人精品在线播放| 久久婷婷麻豆| 欧美一区二区三区免费观看| 欧美一区二区免费视频| 美腿丝袜亚洲色图| 久久国产直播| 欧美国产精品| 欧美极品aⅴ影院| 亚洲一区免费| 亚洲精品你懂的| 午夜精品久久久久久99热| 美女国产精品| 久久久国产精品一区二区三区| 国产精品国产三级国产aⅴ无密码| 欧美激情2020午夜免费观看| 一区二区三区高清| 亚洲一区二区三区免费在线观看| 国产午夜精品一区二区三区视频 | 先锋影音国产精品| 一区二区精品国产| 裸体素人女欧美日韩| 久久香蕉国产线看观看网| 一区二区三区久久精品| 久久久久国产精品一区三寸| 宅男噜噜噜66一区二区| 久久久久久噜噜噜久久久精品 | 久久综合激情| 亚洲激情在线观看| 巨乳诱惑日韩免费av| 欧美日韩精品欧美日韩精品| 欧美影院成人| 欧美日韩少妇| 亚洲一区二区三区影院| 久久久久**毛片大全| 亚洲午夜久久久久久尤物| 久久精品中文字幕一区二区三区| 亚洲精品乱码久久久久久蜜桃91| 亚洲高清视频一区| 亚洲国产精品第一区二区| 一区二区三区精品视频在线观看| 一本久久知道综合久久| 久久夜色精品国产欧美乱| 在线观看一区欧美| 在线视频日韩| 亚洲国产精品t66y| 看欧美日韩国产| 美女尤物久久精品| 在线色欧美三级视频| 欧美制服第一页| 小辣椒精品导航| 在线观看视频一区二区| 久久精品视频免费播放| 男人的天堂成人在线| 一区二区三区毛片| 欧美人与禽性xxxxx杂性| 久久精品国产成人| 久久爱www久久做| 在线播放日韩欧美| 欧美激情视频免费观看| 国内免费精品永久在线视频| 午夜精品久久久久久久久久久久久 | 亚洲一品av免费观看| 日韩午夜一区| 欧美成人综合一区| 中国女人久久久| 亚洲欧美日韩在线播放| 国产专区一区| 91久久精品国产91性色| 欧美亚一区二区| 久久久久久久综合日本| 欧美xart系列高清| 亚洲欧美日韩国产另类专区| 久久精品一二三区| 亚洲色无码播放| 久久精品一区| 亚洲大胆在线| 亚洲主播在线观看| 91久久精品一区二区别| 亚洲欧美激情四射在线日| 最新日韩在线视频| 欧美在线免费看| 亚洲一区二区三区涩| 免费观看成人鲁鲁鲁鲁鲁视频| 亚洲在线视频免费观看| 老司机午夜精品| 欧美有码视频| 国产精品大全| 亚洲第一在线综合在线| 国产日韩欧美综合| 99xxxx成人网| 亚洲精品日韩一| 久久手机精品视频| 欧美综合国产精品久久丁香| 欧美激情精品| 男人的天堂亚洲在线| 国产日韩欧美精品综合| 亚洲免费黄色| 99国产精品久久久久久久久久| 久久精品在线免费观看| 亚洲欧美另类在线观看| 欧美日韩第一区日日骚| 久久综合一区二区三区| 国产片一区二区| 亚洲尤物在线| 亚洲欧美中文在线视频| 欧美大片在线看免费观看| 免费高清在线一区| 精品69视频一区二区三区| 欧美亚洲综合久久| 韩国女主播一区二区三区| 性一交一乱一区二区洋洋av| 亚洲第一区色| 欧美精品一区在线观看| 亚洲国产精品高清久久久| 伊人久久婷婷色综合98网| 欧美在线观看网站| 久久99伊人| 狠狠色狠色综合曰曰| 久久久国产精彩视频美女艺术照福利| 欧美午夜视频在线| 亚洲精品久久久久久久久久久| 91久久亚洲| 欧美喷潮久久久xxxxx| 91久久在线视频| 在线视频精品一区| 国产精品狠色婷| 午夜精品久久久久久99热软件| 亚洲精品免费一区二区三区| 免费精品视频| 一个色综合导航| 久久国产精品久久久久久久久久 | 久久综合伊人77777蜜臀| 国产在线精品一区二区中文 | 久久黄金**| 亚洲国产精品电影在线观看| 一区二区三区久久久| 国产精品久久久久aaaa樱花| 亚洲免费视频成人| 美女视频网站黄色亚洲| 亚洲精品综合在线| 欧美午夜一区二区| 欧美激情亚洲一区| 亚洲欧美日韩国产中文 | 国内一区二区在线视频观看 | 午夜精品一区二区三区在线播放| 久久亚洲一区二区| 亚洲最新视频在线| 国产亚洲精久久久久久| 欧美韩日精品| 久久成人国产| 夜夜夜久久久| 欧美激情第4页| 欧美在线观看一区二区|