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

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>
            久久电影一区| 久久亚裔精品欧美| 正在播放亚洲一区| 久久久噜久噜久久综合| 国产精品v欧美精品v日本精品动漫| 国产自产精品| 欧美影院成人| 亚洲自拍偷拍一区| 国产精品美女主播在线观看纯欲| 亚洲精品少妇网址| 国产精品夫妻自拍| 亚洲精品久久久久中文字幕欢迎你 | 欧美激情a∨在线视频播放| 国产视频一区二区在线观看| 亚洲小少妇裸体bbw| 亚洲国产成人久久| 久久综合九色综合网站| 国产亚洲在线| 久久精品国产69国产精品亚洲| 亚洲手机视频| 国产精品免费一区二区三区在线观看| 在线视频欧美日韩| 亚洲精品久久久久久一区二区 | 激情另类综合| 久久久精品久久久久| 午夜日韩电影| 韩国av一区二区| 久久综合九色| 久久精品主播| 亚洲国产美女| 亚洲精品你懂的| 欧美理论片在线观看| 亚洲视频图片小说| 亚洲午夜未删减在线观看| 国产精品入口66mio| 欧美一级片久久久久久久| 欧美在线日韩| 亚洲精品乱码久久久久久久久 | 欧美在线视频一区| 在线不卡a资源高清| 亚洲高清久久网| 欧美日本不卡视频| 午夜日韩激情| 久久久精品日韩| 日韩亚洲欧美成人| 亚洲欧美国产三级| 亚洲国产精品第一区二区三区| 亚洲激情偷拍| 国产精品一二一区| 欧美精品在线免费| 久久久久久一区二区三区| 日韩视频在线一区二区| 欧美猛交免费看| 午夜精品影院| 久久综合色88| 午夜精品成人在线| 免费看精品久久片| 亚洲欧美经典视频| 久久蜜桃资源一区二区老牛| 一区二区欧美日韩| 久久精品在线观看| 亚洲自拍另类| 老司机免费视频一区二区三区 | 亚洲国产老妈| 国产精品成人一区| 欧美激情导航| 国产精品亚洲综合| 亚洲精美视频| 韩日在线一区| 亚洲制服欧美中文字幕中文字幕| 在线看国产日韩| 亚洲调教视频在线观看| 亚洲欧洲另类| 欧美一区高清| 在线视频中文亚洲| 久久视频一区二区| 欧美尤物巨大精品爽| 欧美伦理一区二区| 另类成人小视频在线| 国产精品免费在线| 日韩视频在线永久播放| 亚洲精品三级| 欧美aⅴ一区二区三区视频| 久久久国产午夜精品| 国产精品成人免费精品自在线观看| 欧美激情在线播放| 精品成人a区在线观看| 一区二区三区视频观看| 亚洲日本va午夜在线影院| 久久精品国产77777蜜臀| 午夜国产精品视频| 国产精品久久久爽爽爽麻豆色哟哟| 亚洲精品男同| 亚洲精选视频在线| 免费成人黄色| 欧美大片在线观看一区二区| 国内一区二区三区| 欧美一级片一区| 久久国产精品久久国产精品| 国产精品免费区二区三区观看| 一区二区三区高清在线观看| 亚洲一区二区三区激情| 欧美日韩在线第一页| 亚洲人成网站999久久久综合| 亚洲人久久久| 欧美日本在线一区| 亚洲精品色婷婷福利天堂| 在线中文字幕一区| 国产精品久久久久秋霞鲁丝| 亚洲免费在线观看视频| 午夜视频一区二区| 国产日韩精品在线| 午夜亚洲视频| 久久午夜激情| 亚洲高清久久久| 狂野欧美激情性xxxx欧美| 亚洲国产精品一区二区第一页| 中文精品在线| 亚洲人精品午夜在线观看| 欧美一区激情| 亚洲电影自拍| 欧美性大战久久久久| 久久国产综合精品| 欧美视频在线播放| 99在线精品视频| 亚洲七七久久综合桃花剧情介绍| 午夜久久一区| 国内精品久久久久影院 日本资源| 亚洲私人影吧| 亚洲欧美日韩一区二区在线| 国产精品试看| 99xxxx成人网| 亚洲一区二区久久| 狠狠色狠狠色综合人人| 老司机aⅴ在线精品导航| 久久激情五月激情| 亚洲精品中文字幕有码专区| 亚洲激情在线观看| 国产精品久久久999| 欧美一区二区三区视频免费| 欧美在线观看网址综合| 亚洲欧洲精品一区二区三区不卡 | 欧美亚洲三级| 亚洲精品无人区| 亚洲在线观看视频网站| 在线 亚洲欧美在线综合一区| 亚洲另类在线视频| 欧美日韩一区二区视频在线| 久久国产精品电影| 欧美网站在线观看| 美女成人午夜| 国产精品实拍| 亚洲免费av电影| 亚洲国产精品久久久久婷婷老年 | 在线视频欧美日韩精品| 国产在线精品一区二区中文| 91久久久一线二线三线品牌| 国产三级精品三级| 日韩视频中文| av成人激情| 欧美片在线观看| 欧美国产精品一区| 国内精品久久久久久 | 久久国产手机看片| 欧美激情一区二区三区| 蘑菇福利视频一区播放| 国产一区二区三区无遮挡| 亚洲一区二区三区精品在线| 一区二区三区久久久| 欧美日韩免费区域视频在线观看| 欧美成人免费一级人片100| 国产亚洲日本欧美韩国| 性欧美1819sex性高清| 久久久精品视频成人| 亚洲国产成人精品女人久久久| 久久精品国产久精国产爱| 久久国产精品99久久久久久老狼 | 久久全国免费视频| 快射av在线播放一区| 亚洲日本欧美| 国产精品高潮粉嫩av| 欧美一区免费视频| 亚洲激精日韩激精欧美精品| 亚洲免费影院| 亚洲国产免费| 韩国成人福利片在线播放| 欧美女主播在线| 久久精品欧洲| 亚洲午夜精品久久久久久浪潮| 毛片一区二区三区| 亚洲中字在线| 欧美a级大片| 亚洲欧美卡通另类91av| 亚洲电影网站| 欧美国产日韩在线| 久久久久久97三级| 午夜伦欧美伦电影理论片| 亚洲精品一品区二品区三品区| 国产亚洲人成网站在线观看| 国产精品久久久91|