Java實作基數排序（RadixSort）的程式碼範例

這篇文章帶給大家的內容是關於Java實作基數排序（RadixSort）的程式碼範例，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

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

基數排序所針對的待排序元素是要有高低位之分的，例如單字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實作基數排序（RadixSort）的程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！