java中基數(shù)排序是什么

這篇文章主要介紹java中基數(shù)排序是什么，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

基數(shù)排序

基數(shù)排序 (Radix Sort) 是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。基數(shù)排序的發(fā)明可以追溯到 1887 年赫爾曼·何樂(lè)禮在打孔卡片制表機(jī) (Tabulation Machine)上的貢獻(xiàn)。

基數(shù)排序法會(huì)使用到桶 (Bucket)，顧名思義，通過(guò)將要比較的位（個(gè)位、十位、百位…），將要排序的元素分配至 0~9 個(gè)桶中，借以達(dá)到排序的作用，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。

算法步驟

1. 將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零

2. 從最低位開(kāi)始，依次進(jìn)行一次排序

3. 從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列

算法演示

動(dòng)畫演示GIF加載有點(diǎn)慢，請(qǐng)稍等片刻^_^

排序動(dòng)畫過(guò)程解釋

1. 基數(shù)排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)

2. 在本例中使用的是 LSD

3. 首先創(chuàng)建編號(hào) 0 ， 1 ，2 ，3 ，4 ，5 ， 6 ，7 ，8 ，9  這 10 個(gè)桶

4. 遍歷整個(gè)數(shù)列，查看數(shù)字的個(gè)位數(shù)，按照先后順序存放在對(duì)應(yīng)編號(hào)的桶中

5. 比如 321 個(gè)位數(shù) 為 1 ，存放在編號(hào) 1 桶中

6. 數(shù)字 1 個(gè)位數(shù) 為  1 ，存放在編號(hào)  1  桶中，同時(shí)存放在 321 上面

7. 遍歷完整個(gè)數(shù)列的個(gè)位數(shù)，將數(shù)字存放在桶中后，按照編號(hào)順序取出數(shù)字，先放入桶中的數(shù)字先取出

8. 然后依次遍歷整個(gè)數(shù)列的十位數(shù)，按照上述個(gè)位數(shù)的操作整理數(shù)列

9. 依次遍歷整個(gè)數(shù)列的百位數(shù)，按照上述個(gè)位數(shù)的操作整理數(shù)列

10. 這樣就完成了 基數(shù)排序

代碼實(shí)現(xiàn)

為了更好的讓讀者用自己熟悉的編程語(yǔ)言來(lái)理解動(dòng)畫，筆者將貼出多種編程語(yǔ)言的參考代碼，代碼全部來(lái)源于網(wǎng)上。

Java代碼實(shí)現(xiàn)

JavaScript代碼實(shí)現(xiàn)

以上是“java中基數(shù)排序是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！