快捷導(dǎo)航

JAVA十大排序算法之基數(shù)排序詳解

更新時(shí)間：2021年08月23日 11:39:07 作者：阿粵Ayue

這篇文章主要介紹了java中的基數(shù)排序，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

基數(shù)排序

常見的數(shù)據(jù)元素一般是由若干位組成的，比如字符串由若干字符組成，整數(shù)由若干位0~9數(shù)字組成。

基數(shù)排序按照從右往左的順序，依次將每一位都當(dāng)做一次關(guān)鍵字，然后按照該關(guān)鍵字對(duì)數(shù)組排序，同時(shí)每一輪排序都基于上輪排序后的結(jié)果；當(dāng)我們將所有的位排序后，整個(gè)數(shù)組就達(dá)到有序狀態(tài)?；鶖?shù)排序不是基于比較的算法。

基數(shù)是什么意思？對(duì)于十進(jìn)制整數(shù)，每一位都只可能是0~9中的某一個(gè)，總共10種可能。那10就是它的基，同理二進(jìn)制數(shù)字的基為2；對(duì)于字符串，如果它使用的是8位的擴(kuò)展ASCII字符集，那么它的基就是256。

基數(shù)排序有兩種方法：

MSD 從高位開始進(jìn)行排序
LSD 從低位開始進(jìn)行排序

對(duì)于大小范圍為0~9的數(shù)的組合（若是兩位數(shù)，就是個(gè)位數(shù)和十位數(shù)的組合），于是可以準(zhǔn)備十個(gè)桶，然后放到對(duì)應(yīng)的桶里，然后再把桶里的數(shù)按照0號(hào)桶到9號(hào)桶的順序取出來(lái)即可。

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

public class RadixSort {
    public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
    public static int[] sort(int[] array) {
        if (array.length < 2) return array;
        //根據(jù)最大值算出位數(shù)
        int max = array[0];
        for (int temp : array) {
            if (temp > max) {
                max = temp;
            }
        }
        //算出位數(shù)digit
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        //創(chuàng)建桶并初始化
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            bucket.add(new ArrayList<>());
        }
        //按照從右往左的順序，依次將每一位都當(dāng)做一次關(guān)鍵字，然后按照該關(guān)鍵字對(duì)數(shù)組排序，每一輪排序都基于上輪排序后的結(jié)果
        int mold = 10;//取模運(yùn)算
        int div = 1;//獲取對(duì)應(yīng)位數(shù)的值
        for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                //獲取個(gè)位/十位/百位......
                int num = (array[j] % mold) / div;
                //把數(shù)據(jù)放入到對(duì)應(yīng)的桶里
                bucket.get(num).add(array[j]);
            }
            //把桶中的數(shù)據(jù)重新寫回去，并把桶的元素清空，開始第二輪排序
            int index = 0;
            for (int k = 0; k < bucket.size(); k++) {
                //桶中對(duì)應(yīng)的數(shù)據(jù)
                ArrayList<Integer> list = bucket.get(k);
                for (int m = 0; m < list.size(); m++) {
                    array[index++] = list.get(m);
                }
                //清除桶
                bucket.get(k).clear();
            }
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}