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

隨感而發

雜七雜八

統計

留言簿(13)

閱讀排行榜

評論排行榜

快速排序學習2(隨機化版本)

學了快速排序的隨機化版本,他和標準的版本沒有什么質的區別,因為快速排序的最壞情況和平均情況效率差太遠,所以用隨機的版本來寫一個更大概率平均的快速排序,也是書上的例子:
直接奉上源代碼:
#include <stdio.h>
#include 
<stdlib.h>
#include 
<time.h>

//化分區間,找到最后元素的排序位置。并返回分隔的點(即最后一數據排序的位置)。
//劃分的區間是[nBegin, nEnd). pData是保存數據的指針
int Partition(int* pData, int nBeging, int nEnd)
{
    
int i = nBeging - 1;    //分隔符號,最后nD保存在這里
    --nEnd;
    
int nD = pData[nEnd]; //比較的數據。
    int nTemp; // 交換用的臨時數據

    
//遍歷數據比較,找到nD的位置,這里注意,比較結果是,
    
//如果i的左邊是小于等于nD的,i的右邊是大于nD的
    for (int j = nBeging; j < nEnd; ++j)
    
{
        
if (pData[j] <= nD)        //如果數據比要比較的小,則在該數據的左邊,與i+1交換
        {
            
++i;                //++i小于nD的數據多一個,所以要加1
            nTemp = pData[i];    //交換數據
            pData[i] = pData[j];
            pData[j] 
= nTemp;
        }

    }


    
//最后不要忘了吧nD和i+1交換,因為這里就是nD的位置咯。
    ++i;
    pData[nEnd] 
= pData[i];
    pData[i] 
= nD;

    
return i;   //返回nD的位置,就是分割的位置。
}


int RandomPartition(int* pData, int nBeging, int nEnd)
{
    
int i = nBeging + rand() % (nEnd - nBeging - 1);
    
int nTemp = pData[i];
    pData[i] 
= pData[nEnd - 1];
    pData[nEnd 
- 1= nTemp;
    
return Partition(pData, nBeging, nEnd);
}


//排序的遞歸調用。
int QuickSortRecursion(int* pData, int nBeging, int nEnd)
{
    
if (nBeging >= nEnd -1)        //如果區域不存在或只有一個數據則不遞歸排序
    {
        
return 1;
    }


    
//這里因為分割的時候,分割點處的數據就是排序中他的位置。
    
//也就是說他的左邊的數據都小于等于他,他右邊的數據都大于他。
    
//所以他不在遞歸調用的數據中。
    int i = RandomPartition(pData, nBeging, nEnd);        //找到分割點
    QuickSortRecursion(pData, nBeging, i);            //遞歸左邊的排序
    QuickSortRecursion(pData, i + 1, nEnd);            //遞歸右邊的排序
    return 1;
}


//快速排序
int QuickSort(int* pData, int nLen)
{
    srand(time(NULL));
    
//遞歸調用,快速排序。
    QuickSortRecursion(pData, 0, nLen);
    
return 1;
}

int main()
{
    
int nData[10= {5,9,3,2,1,6,20,45,88,75};        //測試數據
    QuickSort(nData, 10);            //調用快速排序
    for (int i = 0; i < 10++i)        //輸出結果
    {
        printf(
"%d ", nData[i]);
    }

    printf(
"\n");
    system(
"pause");
    
return 0;
}

posted on 2009-04-23 20:14 shongbee2 閱讀(3802) 評論(2)  編輯 收藏 引用 所屬分類: 數據結構和算法

評論

# re: 快速排序學習2(隨機化版本)[未登錄] 2009-11-05 12:29 cc

int i = nBeging + rand() % (nEnd - nBeging - 1);
是不是要改成
int i = nBeging + rand() % (nEnd - nBeging);

  回復  更多評論   

# re: 快速排序學習2(隨機化版本) 2009-12-17 11:42 feifeicq

pData[i] = pData[nEnd - 1];
pData[nEnd - 1] = nTemp;

要改成:
pData[i] = pData[nEnd];
pData[nEnd] = nTemp;
吧,你用的是pData[nEnd]做key的  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一本久久a久久精品亚洲| 亚洲一区日韩在线| 久久一区激情| 亚洲国产欧美一区二区三区同亚洲| 美女诱惑黄网站一区| 欧美成人一区二区| 亚洲一区二区三区精品视频| 亚洲欧美视频在线| 亚洲精选久久| 久久精品国产v日韩v亚洲| 精品成人一区| 亚洲美女在线国产| 国产精品毛片va一区二区三区| 久久精品国产77777蜜臀 | 在线日韩欧美| 99国内精品久久| 国内精品模特av私拍在线观看| 欧美激情亚洲综合一区| 国产精品va在线播放| 男男成人高潮片免费网站| 欧美日韩在线免费观看| 久久婷婷久久| 欧美四级在线观看| 美女网站久久| 国产精品色婷婷久久58| 欧美高潮视频| 国产小视频国产精品| 亚洲人成在线观看| 国产日韩亚洲欧美| 亚洲免费观看视频| 亚洲国产精品嫩草影院| 亚洲摸下面视频| 99精品欧美| 玖玖玖国产精品| 久久精品2019中文字幕| 欧美日韩在线影院| 亚洲国产精品久久久久婷婷老年| 国产偷国产偷精品高清尤物| 一本色道久久综合精品竹菊 | 亚洲福利免费| 亚洲女人小视频在线观看| 国内精品免费午夜毛片| 欧美三级午夜理伦三级中视频| 久久久一二三| 国产精品性做久久久久久| 欧美va亚洲va香蕉在线| 国产一区二区精品久久99| 99国产精品久久久| 日韩视频在线观看| 免费成人黄色av| 免费在线成人av| 伊人蜜桃色噜噜激情综合| 亚洲欧美日韩一区在线| 香蕉尹人综合在线观看| 国产精品国产| 亚洲在线成人| 久久国产免费| 国产日韩精品久久| 亚洲欧美日韩另类| 久久国产精品99久久久久久老狼| 国产精品欧美日韩一区二区| 亚洲图片你懂的| 亚洲欧美文学| 国产一区二区三区免费在线观看| 欧美一级视频精品观看| 久久久久久久尹人综合网亚洲 | 欧美精品一区二区三区久久久竹菊| 欧美大片在线观看一区二区| 亚洲国产精品va在线观看黑人| 久久综合伊人77777蜜臀| 欧美77777| 一本一本久久| 国产精品美女视频网站| 欧美一级视频| 欧美成人在线免费视频| 99国内精品| 国产精品人人做人人爽人人添| 欧美一区二区高清| 六月婷婷久久| 亚洲免费久久| 国产精品一区二区三区四区 | 西瓜成人精品人成网站| 久久精品五月婷婷| 在线观看日产精品| 欧美裸体一区二区三区| 亚洲午夜小视频| 老司机亚洲精品| 日韩亚洲欧美在线观看| 国产精品日本欧美一区二区三区| 亚久久调教视频| 亚洲二区在线观看| 亚洲一区二区在| 影音先锋一区| 国产精品国产三级国产a| 久久动漫亚洲| 在线视频一区二区| 嫩草国产精品入口| 亚洲一区二区三区中文字幕在线| 国产一区二区三区四区| 欧美精品在线看| 久久激情五月丁香伊人| 日韩视频永久免费| 久久一区免费| 亚洲综合精品一区二区| 亚洲国产一区在线| 国产精品美女诱惑| 欧美国产一区二区| 久久国产一区二区三区| 99热在线精品观看| 亚洲无亚洲人成网站77777| 免费成人av资源网| 午夜精品理论片| 99re成人精品视频| 蜜乳av另类精品一区二区| 亚洲免费人成在线视频观看| 最新中文字幕亚洲| 国外成人在线视频网站| 欧美午夜一区二区| 欧美韩日一区二区| 麻豆精品传媒视频| 久久精品久久综合| 午夜精品久久久久久久99水蜜桃| 99精品热视频| 国外成人性视频| 国产精品美女www爽爽爽| 欧美日韩国产va另类| 久久中文字幕导航| 久久久久久久久久久久久9999| 亚洲免费影视| 亚洲欧美日韩另类| 亚洲欧美成人一区二区三区| 在线视频你懂得一区| 亚洲伦理在线观看| 亚洲精品中文字幕有码专区| 亚洲激情网站| 亚洲精品乱码久久久久久日本蜜臀 | 韩日欧美一区| 国产中文一区| 国模套图日韩精品一区二区| 国产日韩亚洲欧美| 国产一区在线观看视频| 国语自产精品视频在线看一大j8| 国产亚洲制服色| 韩国av一区二区三区| 狠狠色综合网| 亚洲黄色性网站| 日韩一区二区免费高清| 99精品99| 欧美一区二区三区精品| 亚洲视频免费在线| 亚洲午夜日本在线观看| 亚洲自拍16p| 久久久噜噜噜久久人人看| 久久免费国产精品| 欧美高清视频在线播放| 日韩视频二区| 午夜精品久久久久久久99热浪潮| 久久国产精品电影| 免费观看不卡av| 欧美三级视频在线| 国产亚洲欧美一级| 亚洲二区在线| 亚洲性夜色噜噜噜7777| 久久精品久久99精品久久| 男同欧美伦乱| 正在播放亚洲| 国产在线观看一区| 国产精品亚洲综合久久| 伊人久久大香线蕉综合热线| 亚洲日本aⅴ片在线观看香蕉| 亚洲私人黄色宅男| 久久久久久电影| 亚洲人成人77777线观看| 亚洲一区二区视频在线| 久久在线免费观看| 国产精品久久久久久久久久直播| 精品电影在线观看| 亚洲伊人网站| 欧美激情亚洲激情| 亚洲一二三区在线观看| 免费久久精品视频| 国产欧美日韩综合一区在线观看 | 久久综合久久综合九色| 免费成年人欧美视频| 国产精品久久久久久久久搜平片| 黄色成人av网| 亚洲一区区二区| 欧美激情第二页| 欧美亚洲在线视频| 欧美日韩四区| 亚洲激情专区| 久久久精品一区| 一区二区日韩| 欧美xxx成人| 尤物视频一区二区| 久久不射电影网| 亚洲一区二区黄| 欧美色中文字幕| 中国成人亚色综合网站| 欧美激情亚洲综合一区|