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

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樞紐元的選?。?br>111. 選取第一個(gè)元素做樞紐元:對(duì)于(部分)預(yù)排序的序列運(yùn)行時(shí)間O(N^2)
122. 隨機(jī)生成樞紐元:能避免上述問(wèn)題,但是產(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)草 閱讀(2906) 評(píng)論(8)  編輯 收藏 引用 所屬分類: Algorithms

評(píng)論

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

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

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

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

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

@Linsea
是以2為底的logN,我想有的時(shí)候沒(méi)寫(xiě)是默認(rèn)是2吧,因?yàn)槎鏄?shù)一般涉及的都是以2為底的指數(shù)函數(shù),反過(guò)來(lái)也是以2為底的對(duì)數(shù)函數(shù)。

具體的解釋我放在原日志最下端了,因?yàn)槲抑荒芤詧D片的格式插入數(shù)學(xué)公式,所以就沒(méi)有辦法放在回復(fù)里了,你看一下,有問(wèn)題再聯(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
謝謝?。】赡苁菫g覽器兼容性的關(guān)系!不過(guò)在改進(jìn)了!
  回復(fù)  更多評(píng)論   

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

我寫(xiě)的快排,簡(jiǎn)單的理解,沒(méi)你的這么深??梢缘脑?,幫我看看!
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>
            亚洲视频每日更新| 国产一区视频观看| 欧美激情网友自拍| 国产在线视频欧美| 性高湖久久久久久久久| 亚洲国产精品久久久久秋霞蜜臀| 夜久久久久久| 欧美日韩精品一区二区天天拍小说 | 国产精品久久久久一区| 亚洲日韩视频| 欧美激情自拍| 欧美激情综合色综合啪啪| 亚洲精品国产系列| 亚洲国产日本| 欧美激情国产日韩| 亚洲精品一二区| 亚洲国产清纯| 国产精品久久久久久久7电影| 亚洲影音一区| 亚洲午夜av在线| 国产精品一区亚洲| 欧美在线影院在线视频| 国产精品夫妻自拍| 女主播福利一区| 亚洲高清网站| 91久久精品www人人做人人爽| 免费黄网站欧美| 亚洲精品免费在线播放| 亚洲人被黑人高潮完整版| 欧美伦理视频网站| 亚洲欧美综合| 久久9热精品视频| 亚洲国产国产亚洲一二三| 亚洲日本精品国产第一区| 欧美亚洲第一区| 久久精品伊人| 欧美不卡视频| 亚洲一区二区综合| 欧美在线免费观看亚洲| 亚洲精品美女久久7777777| 日韩一二三在线视频播| 国产欧美日韩不卡| 欧美激情一区二区三区在线视频| 国产精品国产三级国产专区53 | 今天的高清视频免费播放成人| 欧美成人一品| 国产精品jvid在线观看蜜臀| 久久国产精品第一页| 免费成人在线视频网站| 亚洲永久在线观看| 久久久xxx| 亚洲综合首页| 久久视频在线视频| 亚洲免费人成在线视频观看| 久热精品在线| 久久国产精品久久国产精品| 欧美极品欧美精品欧美视频| 久久精品综合一区| 欧美三级网址| 欧美黄在线观看| 国产一区二区黄| 夜夜嗨av一区二区三区四季av| 精品成人在线视频| 亚洲免费影视| 亚洲在线视频一区| 欧美激情视频网站| 久久久久久亚洲精品中文字幕| 欧美视频亚洲视频| 91久久国产综合久久| 激情av一区| 亚洲欧美在线一区二区| 99精品国产99久久久久久福利| 午夜精品区一区二区三| 一区二区三区四区五区精品视频| 久久永久免费| 久久综合伊人77777麻豆| 国产精品资源在线观看| 亚洲图中文字幕| 亚洲一二三区在线观看| 欧美另类videos死尸| 欧美激情精品久久久久久| 国内精品视频在线观看| 亚洲综合精品一区二区| 亚洲一区二区三区在线观看视频 | 久久精品视频免费| 亚洲欧美精品suv| 欧美视频中文一区二区三区在线观看| 亚洲第一区色| 亚洲国产天堂久久综合| 欧美在线观看网址综合| 久久国产视频网站| 国产日产精品一区二区三区四区的观看方式 | 久久久久青草大香线综合精品| 欧美综合国产| 国产日本亚洲高清| 久久成人精品视频| 久久综合色一综合色88| 激情综合久久| 美国三级日本三级久久99| 欧美国产视频一区二区| 亚洲美女区一区| 欧美三级不卡| 一区二区不卡在线视频 午夜欧美不卡在 | 久久网站免费| 国内激情久久| 久久久999精品| 欧美国产成人在线| 日韩视频在线免费| 欧美日韩一区二区视频在线| 亚洲影院污污.| 久久综合久久久| 亚洲精品欧美一区二区三区| 欧美久久九九| 亚洲欧美中文另类| 欧美国产欧美亚洲国产日韩mv天天看完整 | 欧美综合二区| 在线免费不卡视频| 欧美了一区在线观看| 亚洲免费视频中文字幕| 免费日韩av片| 亚洲午夜国产一区99re久久 | 亚洲尤物在线视频观看| 国产视频一区在线| 蜜臀av性久久久久蜜臀aⅴ四虎| 亚洲日本一区二区三区| 午夜亚洲性色视频| 欧美精品二区| 亚洲欧美日韩综合国产aⅴ| 免费观看日韩| 亚洲一区久久久| 狠狠v欧美v日韩v亚洲ⅴ| 欧美激情区在线播放| 欧美一区二区女人| 亚洲日本中文字幕区| 久久国产一区| 亚洲视频日本| 亚洲福利视频三区| 国产精品亚洲片夜色在线| 免播放器亚洲一区| 亚洲欧美国产制服动漫| 最新成人在线| 久久久777| 亚洲小视频在线| 亚洲国产清纯| 国产婷婷97碰碰久久人人蜜臀| 欧美成人一区二区三区在线观看| 校园激情久久| 亚洲一区二区四区| 亚洲精品中文字幕在线| 狂野欧美激情性xxxx欧美| 亚洲欧美日韩国产中文在线| 亚洲精品视频免费观看| 在线免费不卡视频| 国产综合网站| 国产欧美日韩免费| 国产精品美女主播| 欧美色区777第一页| 欧美另类videos死尸| 欧美电影美腿模特1979在线看| 欧美中文字幕精品| 亚洲欧美日韩另类| 亚洲午夜电影| 一区二区三区精品视频| 亚洲乱码国产乱码精品精| 亚洲激情不卡| 亚洲第一网站| 亚洲高清自拍| 亚洲激情小视频| 亚洲黄色免费电影| 欧美国产一区二区| 欧美成年人视频网站欧美| 美女精品在线| 欧美大片在线看| 欧美福利一区| 亚洲激情电影中文字幕| 亚洲第一级黄色片| 亚洲韩日在线| 一本色道久久综合亚洲精品婷婷| 亚洲免费av片| 一区二区动漫| 香蕉久久夜色精品国产| 欧美一进一出视频| 久久久999| 欧美成人免费视频| 欧美成人dvd在线视频| 欧美刺激午夜性久久久久久久| 欧美成人情趣视频| 欧美日韩高清在线| 国产精品劲爆视频| 国产精品制服诱惑| 在线观看欧美成人| 亚洲日本欧美在线| 免费不卡亚洲欧美| 麻豆成人精品| 欧美激情按摩| 国产精品高清网站| 国精产品99永久一区一区| 亚洲欧洲日产国产综合网| 一区二区三区久久久| 欧美在线播放一区|