• <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>

            liyuxia713

            蹣跚前行者

            常用鏈接

            統(tǒng)計

            Algorithms

            C++

            最新評論

            基本排序算法及分析(六):桶式排序

            桶式排序是對一個有n個整型元素的數組a[n],其中對任意i,0 <= a[i] <= m的特殊排序算法。
            可以對 n==m, n != m分別處理。寫代碼時需要注意的的是a[i]是訪問第i-1個元素,而非第i個。
             1/************************************************************************************/
             2/* Bucket_Sort.h  桶式排序算法                                                      */
             3/* 問題:對一個有n個整型元素a[0],a[1],…,a[n-1]的數組排序,其中0 <= a[i] <= m,任意i */ 
             4/* 程序:運行時間為O(m+n),輔助空間為O(m)                                            */
             5/* 當 n=m 時特殊處理,運行時間為O(N), 輔助空間為O(1)                                */
             6/************************************************************************************/
             7
             8#include <vector>
             9
            10/*m != n */
            11void Bucket_Sort_m(int *a, int n, int m) 
            12{          
            13    std::vector<int> temp(m,0); 
            14    int i;
            15    for(i = 0; i != n; ++i)  //遍歷a[]
            16        ++temp[a[i]-1]; //如果有對應于下標的值,標記為1,否則為0
            17
            18    i = 0
            19    for(int j = 1; j <= m; ++j) //遍歷temp向量
            20        if(temp[j-1]) a[i++= j;
            21        
            22    temp.clear();
            23}

            24
            25/* m == n */
            26/* 最后的結果是a[i-1] = i */
            27void Bucket_Sort(int *a,int n)
            28{
            29    for(int i = 1; i <= n; ++i)
            30    {
            31        while(a[i-1!= i) 
            32        {
            33             int temp = a[a[i-1]-1];
            34             a[a[i-1]-1= a[i-1];
            35             a[i-1= temp;
            36        }

            37        /* 偽代碼:如果假設可以通過a[i]訪問數組的第i個元素,而不是第i-1個 */
            38        /*while(a[i] != i) 
            39        {
            40             int temp = a[a[i]];
            41             a[a[i]] = a[i];
            42             a[i] = temp;
            43        }
            44        */

            45    }
                
            46}

            posted on 2009-04-23 19:03 幸運草 閱讀(1270) 評論(0)  編輯 收藏 引用 所屬分類: Algorithms

            青青草国产97免久久费观看| 中文字幕久久精品无码| 久久天天躁狠狠躁夜夜2020老熟妇 | 久久精品九九亚洲精品天堂| 久久精品国产91久久麻豆自制 | 国内精品伊人久久久久网站| 伊人色综合久久天天网| 777米奇久久最新地址| 婷婷久久综合九色综合绿巨人| 思思久久99热只有频精品66| 91精品国产色综久久| 亚洲va中文字幕无码久久| 国产精品免费久久久久影院| 久久精品国产亚洲av高清漫画 | 青青草原综合久久大伊人| 国产精品久久久久jk制服| 漂亮人妻被中出中文字幕久久 | 久久AV无码精品人妻糸列| 久久精品无码专区免费| 99久久国产热无码精品免费| 香蕉久久影院| 青青青青久久精品国产| 久久精品国产亚洲AV电影| 欧美粉嫩小泬久久久久久久| 久久r热这里有精品视频| 久久精品无码一区二区WWW| 欧美精品一区二区久久 | 丁香色欲久久久久久综合网| 免费精品久久久久久中文字幕| 国产精品岛国久久久久| 日产精品久久久久久久性色| 久久婷婷人人澡人人爽人人爱 | 国产成人精品久久二区二区| 亚洲精品高清国产一线久久| 久久久亚洲裙底偷窥综合| 中文国产成人精品久久亚洲精品AⅤ无码精品| 国产精品美女久久久| 久久青草国产精品一区| 999久久久免费国产精品播放| 久久精品国产亚洲网站| 国产精品成人99久久久久|