基数ソート (RadixSort) の Java 実装のコード例

この記事では、基数ソート (RadixSort) の Java 実装に関するコード例を紹介します。必要な方は参考にしていただければ幸いです。

基数ソートではバケット ソートとカウンティング ソートのいずれかが使用されるため、基数ソートはバケット ソートとカウンティング ソートから派生したものです。

基数ソートでソートする要素は、上位と下位に分割する必要があります。たとえば、adobe、activiti、および activiti という単語は、ascll コードに基づいています。

ここで質問をしてみましょう。辞書内の単語をどのように並べ替えるのですか?

たとえば、次のような単語があります:

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

どうやって並べ替えますか? ここで基数ソートを使用できます。基数ソートの原理は、要素を上位と下位に分割することです。 Adobe などの 1 つの個体は A、d、o、b、e に分割され、アルゴリズムは A、l、g、o、r、i、t、h、m に分割されます。それらを右から左に順番に比較します。つまり、Can です。ただし、Adobe と Algorithm は長さが異なるため、ここで直接比較することはできません。そのため、比較する前に、最も長い要素の長さを見つけて、残りの短い要素を同じ長さにする必要があります:

Adobe0000

アルゴリズム

このようにして、右から左へ、0:m、0:h、0:t、0:i、e:r、b:o、oの比較を形成できます。 : g,d:l,A:A、Adobe > Algorihtm

原理は次の図でより明確になります:

から上の図から、基数ソートは右から左に比較されることがわかります (つまり、プログラムの実装では何度も走査する必要があります)。特定の走査回数は、最長の要素の長さに依存します。右から左へ 左の各ビットの要素を比較するには、バケット ソートまたはカウンティング ソートの時間計算量を使用できます。最大要素長を K とすると、時間計算量は次のようになります。基数ソートは O(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;
    }
}

ソートする前に、要素の最大長を見つけてループ数を決定し、最大値に基づいて短い要素を完成させる必要があることに注意してください。要素の長さ。

プログラム実行結果:

以上が基数ソート (RadixSort) の Java 実装のコード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。