Java實現(xiàn)基數(shù)排序的方法

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

基數(shù)排序算是桶排序和計數(shù)排序的衍生吧，因為基數(shù)排序里面會用到這兩種其中一種。

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

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

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

"Java", "Mongodb", "Redis", "Kafka", "javascript", "mysql", "mybatis", "kindle", "rpc", "Algorithm", "mergeSort", "quickSort", "Adobe"

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

Adobe0000

Algorithm

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

跟著以下的圖片會更清楚原理：

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

以下是我的Java實現(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: 計數(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: 計數(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: 自動補全單詞
     * @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: 獲取字符串最大的長度
     * @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;
    }
}

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

程序執(zhí)行結果：

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