Java實現基數排序的方法

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

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

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

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

比如我們現在有如下單詞：

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

我們要怎么對它排序呢，這里就可以用到基數排序了，基數排序的原理就是我們將一個元素按高低位分成單個個體，比如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

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

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

以下是我的Java實現：

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: 基數排序（單詞）
     * @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: 計數排序（單詞）
     * @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: 基數排序（純數字）
     * @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: 計數排序（純數字）
     * @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: 獲取最大的數字
     * @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;
    }
}

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

程序執行結果：

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