這篇文章主要介紹了web開(kāi)發(fā)中基數(shù)排序是什么意思，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)建站專注于洛浦網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供洛浦營(yíng)銷型網(wǎng)站建設(shè)，洛浦網(wǎng)站制作、洛浦網(wǎng)頁(yè)設(shè)計(jì)、洛浦網(wǎng)站官網(wǎng)定制、小程序開(kāi)發(fā)服務(wù)，打造洛浦網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供洛浦網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。

基數(shù)排序的例子

什么是基數(shù)排序呢？

考慮一下，雖然我們不能直接將所有范圍內(nèi)的數(shù)字都使用count數(shù)組進(jìn)行排序，但是我們可以考慮按數(shù)字的位數(shù)來(lái)進(jìn)行n輪count排序，每一輪都只對(duì)數(shù)字的某一位進(jìn)行排序。

最終仍然可以得到結(jié)果，并且還可以擺脫count數(shù)組大小的限制，這就是基數(shù)排序。

假如我們現(xiàn)在數(shù)組的元素是：1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。

先看動(dòng)畫(huà)，看下最直觀的基數(shù)排序的過(guò)程：

在上面的例子中，我們先對(duì)個(gè)位進(jìn)行count排序，然后對(duì)十位進(jìn)行count排序，然后是百位和千位。

最后生成最終的排序結(jié)果。

基數(shù)排序的java代碼實(shí)現(xiàn)

因?yàn)榛鶖?shù)排序?qū)嶋H上是分別按位數(shù)的count排序。所以我們可以重用之前寫(xiě)的count排序的代碼，只是需要進(jìn)行一些改造。

doCountingSort方法除了傳入數(shù)組外，還需要傳入排序的位數(shù)digit，我們用1，10，100，1000來(lái)表示。

看一下改造過(guò)后的doCountingSort方法：

   public void doRadixSort(int[] array, int digit){int n = array.length;// 存儲(chǔ)排序過(guò)后的數(shù)組int output[] = new int[n];// count數(shù)組，用來(lái)存儲(chǔ)統(tǒng)計(jì)各個(gè)元素出現(xiàn)的次數(shù)int count[] = new int[10];
        Arrays.fill(count,0);
        log.info("初始化count值:{}",count);// 將原始數(shù)組中數(shù)據(jù)出現(xiàn)次數(shù)存入count數(shù)組for (int i=0; i<n; ++i) {
            count[(array[i]/digit)%10]++;
        }
        log.info("count之后count值:{}",count);// 這里是一個(gè)小技巧，我們根據(jù)count中元素出現(xiàn)的次數(shù)計(jì)算對(duì)應(yīng)元素第一次應(yīng)該出現(xiàn)在output中的下標(biāo)。//這里的下標(biāo)是從右往左數(shù)的for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("整理count對(duì)應(yīng)的output下標(biāo):{}",count);// 根據(jù)count中的下標(biāo)，構(gòu)建排序后的數(shù)組//插入一個(gè)之后，相應(yīng)的count下標(biāo)要減一for (int i = n-1; i>=0; i--)
        {
            output[count[(array[i]/digit)%10]-1] = array[i];
            count[(array[i]/digit)%10]--;
        }
        log.info("構(gòu)建output之后的output值:{}",output);//將排序后的數(shù)組寫(xiě)回原數(shù)組for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

跟count排序變化不大，區(qū)別就是這里我們需要使用count[(array[i]/digit)%10]，來(lái)對(duì)每一位進(jìn)行排序。

另外，為了計(jì)算出位數(shù)digit的值，我們還需要拿到數(shù)組中最大元素的值：

public int getMax(int[] array){int mx = array[0];for (int i = 1; i < array.length; i++)if (array[i] > mx){
                mx = array[i];
            }return mx;
    }

看下怎么調(diào)用：

    public static void main(String[] args) {int[] array= {1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793};
        RadixSort radixSort=new RadixSort();
        log.info("radixSort之前的數(shù)組為:{}",array);//拿到數(shù)組的最大值，用于計(jì)算digitint max = radixSort.getMax(array);//根據(jù)位數(shù)，遍歷進(jìn)行count排序for (int digit = 1; max/digit > 0; digit *= 10){
            radixSort.doRadixSort(array,digit);
        }
    }

看下輸出結(jié)果：

很好，結(jié)果都排序了。

基數(shù)排序的時(shí)間復(fù)雜度

從計(jì)算過(guò)程我們可以看出，基數(shù)排序的時(shí)間復(fù)雜度是O(d*(n+b)) ，其中b是數(shù)字的進(jìn)制數(shù)，比如上面我們使用的是10進(jìn)制，那么b=10。

d是需要循環(huán)的輪數(shù)，也就是數(shù)組中最大數(shù)的位數(shù)。假如數(shù)組中最大的數(shù)字用K表示，那么d=logb(k)。

綜上，基數(shù)排序的時(shí)間復(fù)雜度是O((n+b) * logb(k))。

當(dāng)k <= nc，其中c是常量時(shí)，上面的時(shí)間復(fù)雜度可以近似等于O(nLogb(n))。

考慮下當(dāng)b=n的情況下，基數(shù)排序的時(shí)間復(fù)雜度可以近似等于線性時(shí)間復(fù)雜度O(n)。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“web開(kāi)發(fā)中基數(shù)排序是什么意思”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

網(wǎng)站名稱：web開(kāi)發(fā)中基數(shù)排序是什么意思
URL地址：http://vcdvsql.cn/article20/pdigjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司、微信小程序、面包屑導(dǎo)航、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)