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

liyuxia713

蹣跚前行者

常用鏈接

統(tǒng)計(jì)

Algorithms

C++

最新評論

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

快速排序:
 1/*----------------------------------------------------------------------------------------------
 2Quick_sort.h
 3快速排序:確定一個(gè)樞紐元,一次遍歷后將數(shù)組劃分成兩個(gè)部分,第一部分均比樞紐元小
 4         第二部分都比樞紐元大,然后對這兩個(gè)數(shù)組進(jìn)行快速排序,是一種遞歸的方法
 5平均運(yùn)行時(shí)間O(Nlog(N)),最壞運(yùn)行時(shí)間O(N^2)
 6最壞情形:對于預(yù)排序的序列。
 7對與樞紐元相等的元素處理:
 8    i,j都停止:會比較相等元素,但是可以劃分成長度相當(dāng)?shù)膬蓚€(gè)子數(shù)組
 9    i,j都不停止,不會比較相等元素,但是可能產(chǎn)生長度不平衡的兩個(gè)子數(shù)組(與樞紐元相等的元素較多時(shí))
10樞紐元的選取:
111. 選取第一個(gè)元素做樞紐元:對于(部分)預(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è)位置的元素,按順序擺好,一會兒begin,end位置的元素就無需參加比較
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)草 閱讀(2906) 評論(8)  編輯 收藏 引用 所屬分類: Algorithms

評論

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

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

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

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

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

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

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

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

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

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

@我是大熊

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

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

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

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

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

# 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ù)  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            午夜精品一区二区三区在线视| 亚洲日本一区二区三区| 小处雏高清一区二区三区 | 欧美成人性网| 久久久91精品国产一区二区精品| 午夜精品国产| 久久久久国产免费免费| 久久久青草婷婷精品综合日韩| 久久精品日产第一区二区| 玖玖国产精品视频| 亚洲第一福利视频| 亚洲国产电影| 亚洲一区二区三区成人在线视频精品| 日韩一级黄色大片| 欧美一区激情视频在线观看| 久久影院午夜片一区| 欧美另类久久久品 | 18成人免费观看视频| 亚洲人成网站999久久久综合| 亚洲午夜在线| 久久人人97超碰精品888| 亚洲国产精品尤物yw在线观看 | 国产精品美女久久久久久免费| 国产亚洲精品久久久久动| 亚洲激情av在线| 性亚洲最疯狂xxxx高清| 欧美大片在线看| 亚洲欧美一级二级三级| 欧美xxx成人| 国产丝袜一区二区| 在线视频欧美日韩| 免费观看成人| 亚洲在线成人| 欧美日本韩国在线| 韩国三级在线一区| 午夜免费电影一区在线观看| 久久久7777| 国产日韩欧美亚洲| 国产精品va在线播放| 在线播放日韩专区| 欧美在线视频在线播放完整版免费观看 | 一区二区三区国产精品| 久久综合九色综合网站 | 欧美成人免费在线视频| 国产日韩精品一区二区浪潮av| 亚洲区第一页| 久久躁日日躁aaaaxxxx| 亚洲欧美日本国产有色| 欧美日韩视频第一区| 亚洲激情欧美| 女女同性精品视频| 久久精品国产2020观看福利| 国产精品qvod| 亚洲愉拍自拍另类高清精品| 亚洲精品亚洲人成人网| 免费看黄裸体一级大秀欧美| 国外精品视频| 老鸭窝91久久精品色噜噜导演| 欧美在线视屏| 国产欧美一区二区三区视频| 亚洲免费综合| 亚洲一区国产视频| 欧美天堂亚洲电影院在线观看| 一本色道久久综合狠狠躁篇怎么玩| 亚洲承认在线| 欧美激情一区二区三区高清视频| 91久久久久| 亚洲人成精品久久久久| 欧美剧在线观看| 一区二区久久久久| 一区二区三区视频在线| 国产精品久久久久国产a级| 亚洲欧美另类国产| 亚洲在线视频观看| 国产综合色在线| 久久视频在线看| 另类av导航| 亚洲最快最全在线视频| 亚洲图片欧洲图片日韩av| 国产欧美精品日韩| 噜噜噜91成人网| 免费成人激情视频| 一本色道久久99精品综合| 亚洲午夜国产成人av电影男同| 国产麻豆综合| 免费欧美在线视频| 欧美日韩国产在线看| 午夜精品福利一区二区三区av| 午夜宅男久久久| 亚洲黄色免费电影| 国产精品99久久久久久有的能看| 国产日韩欧美成人| 亚洲第一福利视频| 亚洲激情成人网| 亚洲图色在线| 欧美性片在线观看| 欧美亚洲免费电影| 久久久免费精品| 亚洲免费av片| 午夜精品一区二区三区在线视| 在线观看欧美黄色| 亚洲日本成人在线观看| 国产在线视频欧美一区二区三区| 亚洲国产视频一区二区| 国产精品视频区| 免费观看成人鲁鲁鲁鲁鲁视频| 欧美理论片在线观看| 久久婷婷蜜乳一本欲蜜臀| 欧美激情一区在线| 欧美在线首页| 国产精品va在线播放| 亚洲第一成人在线| 国外成人网址| 亚洲视频二区| 99视频精品全部免费在线| 欧美中文在线观看国产| 正在播放欧美一区| 米奇777超碰欧美日韩亚洲| 欧美一级在线播放| 欧美日韩精品三区| 欧美激情视频在线播放| 好吊视频一区二区三区四区| 亚洲一区二区三区精品视频 | 久久天天躁夜夜躁狠狠躁2022| 欧美亚洲免费| 国产精品久久久久免费a∨大胸| 亚洲经典在线| 亚洲欧洲一区二区三区| 久久午夜精品| 男人插女人欧美| 狠狠色狠狠色综合日日小说| 亚洲欧美日韩在线高清直播| 亚洲一级黄色| 欧美日韩精品免费看| 亚洲毛片在线看| 99视频热这里只有精品免费| 欧美阿v一级看视频| 欧美激情精品久久久久久免费印度 | 农村妇女精品| 亚洲第一在线视频| 久久久久久久久久久一区| 美腿丝袜亚洲色图| 亚洲国产mv| 欧美激情一区二区三区在线视频观看 | 久久婷婷成人综合色| 欧美久久一级| 亚洲经典视频在线观看| 欧美91视频| 亚洲级视频在线观看免费1级| 一区二区三区在线免费视频| 性欧美大战久久久久久久免费观看 | 亚洲欧美日韩在线| 久久精品国产亚洲a| 国产精品一区二区三区乱码| 亚洲欧美成人一区二区在线电影| 欧美影院视频| 亚洲高清123| 欧美精品一区在线发布| 这里是久久伊人| 久久爱www.| 伊人精品视频| 欧美区视频在线观看| 一区二区三区 在线观看视| 亚洲女同在线| 狠狠干狠狠久久| 欧美成人精品在线观看| 宅男精品导航| 久热精品视频在线| aⅴ色国产欧美| 国产日韩欧美三级| 美女成人午夜| 亚洲一区黄色| 欧美激情成人在线| 亚洲欧美综合国产精品一区| 狠狠色综合色综合网络| 欧美激情中文不卡| 亚洲欧美中文在线视频| 91久久精品国产| 久久国产精品久久久久久久久久| 亚洲二区三区四区| 国产欧美日韩在线播放| 欧美国产精品| 欧美一区二区三区另类| 亚洲国产专区校园欧美| 亚洲欧美日韩国产成人精品影院| 一色屋精品视频在线看| 国产精品高潮呻吟久久av无限 | 麻豆成人在线播放| 亚洲欧美国产高清va在线播| 亚洲观看高清完整版在线观看| 国产精品亚洲综合| 欧美欧美天天天天操| 久久一综合视频| 午夜日韩激情| 日韩手机在线导航| 欧美粗暴jizz性欧美20| 久久久精品久久久久| 亚洲影院免费| 日韩小视频在线观看专区| 在线观看91精品国产麻豆|