這篇文章給大家分享的是有關(guān)Java實(shí)現(xiàn)基數(shù)排序的方法的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過來看看吧。

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供曲阜網(wǎng)站建設(shè)、曲阜做網(wǎng)站、曲阜網(wǎng)站設(shè)計(jì)、曲阜網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、曲阜企業(yè)網(wǎng)站模板建站服務(wù)，10年曲阜做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

基數(shù)排序算是桶排序和計(jì)數(shù)排序的衍生吧，因?yàn)榛鶖?shù)排序里面會(huì)用到這兩種其中一種。

基數(shù)排序針對(duì)的待排序元素是要有高低位之分的，比如單詞adobe，activiti，activiti就高于adobe，這個(gè)是根據(jù)ascll碼來的。

現(xiàn)在我們可以提出一個(gè)問題，怎樣對(duì)字典里面的單詞進(jìn)行排序呢？

比如我們現(xiàn)在有如下單詞：

"Java", "MongoDB", "redis", "Kafka", "javascript", "MySQL", "mybatis", "kindle", "rpc", "Algorithm", "mergeSort", "quickSort", "Adobe"

我們要怎么對(duì)它排序呢，這里就可以用到基數(shù)排序了，基數(shù)排序的原理就是我們將一個(gè)元素按高低位分成單個(gè)個(gè)體，比如Adobe我們就分成A,d,o,b,e，Algorithm我們就分成A,l,g,o,r,i,t,h,m，然后我們從右往左，依次比較即可。但是這里Adobe和Algorithm并不能直接比較，因?yàn)樗麄兊拈L(zhǎng)短不一，所以在比較之前我們應(yīng)該找到最長(zhǎng)的元素的長(zhǎng)度，然后將其余短的元素補(bǔ)全到一樣長(zhǎng)：

Adobe0000

Algorithm

這樣才可以形成比較，從右往左,0:m,0:h,0:t,0:i,e:r,b:o,o:g,d:l,A:A，我們就可以比較出來Adobe > Algorihtm

跟著以下的圖片會(huì)更清楚原理：

從上圖我們可以看出，基數(shù)排序會(huì)從右往左依次比較（即在我們的程序?qū)崿F(xiàn)里面需要遍歷很多次），而具體要遍歷多少次則取決于最長(zhǎng)的元素有多長(zhǎng)，從右往左對(duì)每個(gè)位的元素比較可以用到桶排序或計(jì)數(shù)排序，桶排序和計(jì)數(shù)排序的時(shí)間復(fù)雜度都是O(n)，假設(shè)最大的元素長(zhǎng)度為K，則基數(shù)排序的時(shí)間復(fù)雜度為O(k * n)，而k一般不會(huì)有多大，可以視為常量，所以基數(shù)排序的時(shí)間復(fù)雜度也是O(n)。

以下是我的Java實(shí)現(xiàn)：

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 14:58
 **/
public class RadixSort {
    public static void main(String[] args) {
        /*int[] numbers = {19, 36, 24, 10, 9, 29, 1, 0, 3, 60, 100, 1001, 999, 520, 123, 96};
        radixSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }*/
        String[] words = {"Java", "Mongodb", "Redis", "Kafka", "javascript", "mysql", "mybatis", "kindle", "rpc", "Algorithm", "mergeSort", "quickSort", "Adobe"};
//        String[] words = {"Java", "mongodb", "Kafka"};
        radixSort(words);
        for (String word : words) {
            System.out.println(word.replaceAll("0", ""));
        }
    }
    /**
     * @Author: xingrui
     * @Description: 基數(shù)排序（單詞）
     * @Date: 15:53 2019/1/30
     */
    private static void radixSort(String[] words){
        int exp = 0;
        int maxLength = getMaxLength(words);
        autoComplete(words, maxLength);
        for(exp = 1; exp <= maxLength; exp++){
            countingSort(words, exp);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 計(jì)數(shù)排序（單詞）
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(String[] words, int exp){
        int n = words.length;
        String[] r = new String[n];
        int[] c = new int[122];
        for(int i = 0; i < n; ++i){
            int asc = (byte)words[i].charAt(words[i].length() - exp);
            c[asc]++;
        }
        for(int i = 1; i < 122; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int asc = (byte)words[i].charAt(words[i].length() - exp);
            int index = c[asc];
            r[index - 1] = words[i];
            c[asc]--;
        }
        for(int i = 0; i < n; ++i){
            words[i] = r[i];
        }
    }
    /**
     * @Author: xingrui
     * @Description: 基數(shù)排序（純數(shù)字）
     * @Date: 15:00 2019/1/30
     */
    private static void radixSort(int[] numbers){
        int exp = 0;
        int maxNumber = getMaxNumber(numbers);
        for(exp = 1; maxNumber/exp > 0; exp *= 10){
            countingSort(numbers, exp);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 計(jì)數(shù)排序（純數(shù)字）
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers, int exp){
        int n = numbers.length;
        int[] r = new int[n];
        int[] c = new int[10];
        for(int i = 0; i < n; ++i){
            c[numbers[i]/exp % 10]++;
        }
        for(int i = 1; i < 10; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i] / exp % 10];
            r[index - 1] = numbers[i];
            c[numbers[i] / exp % 10]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
    /**
     * @Author: xingrui
     * @Description: 自動(dòng)補(bǔ)全單詞
     * @Date: 16:38 2019/1/30
     */
    private static void autoComplete(String[] words, int maxLength){
        int i = 0;
        for (String word : words) {
            if(word.length() < maxLength){
                int value = maxLength - word.length();
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < value; ++j){
                    sb.append("0");
                }
                words[i] = word + sb;
            }
            i++;
        }
    }
    /**
     * @Author: xingrui
     * @Description: 獲取字符串最大的長(zhǎng)度
     * @Date: 15:56 2019/1/30
     */
    private static int getMaxLength(String[] words){
        int maxLength = words[0].length();
        for(int i = 1; i < words.length; ++i){
            if(words[i].length() > maxLength)
                maxLength = words[i].length();
        }
        return maxLength;
    }
    /**
     * @Author: xingrui
     * @Description: 獲取最大的數(shù)字
     * @Date: 15:56 2019/1/30
     */
    private static int getMaxNumber(int[] numbers){
        int maxNumber = numbers[0];
        for(int i = 1; i < numbers.length; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        return maxNumber;
    }
}

其中需要注意就是在排序之前需要找到最大的元素長(zhǎng)度以確定循環(huán)次數(shù)和根據(jù)最大元素長(zhǎng)度補(bǔ)全比較短的元素。

程序執(zhí)行結(jié)果：

感謝各位的閱讀！關(guān)于Java實(shí)現(xiàn)基數(shù)排序的方法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！