Codebeispiel für die Java-Implementierung der Radix-Sortierung (RadixSort)

Dieser Artikel bietet Ihnen ein Codebeispiel für die Implementierung der Radix-Sortierung in Java. Ich hoffe, dass er Ihnen als Referenz dienen wird.

Die Radix-Sortierung ist eine Ableitung der Bucket-Sortierung und der Counting-Sortierung, da einer dieser beiden Typen bei der Radix-Sortierung verwendet wird.

Die durch Basissortierung zu sortierenden Elemente müssen hohe und niedrige Ziffern haben. Beispielsweise sind die Wörter „adobe“, „activiti“ und „activiti“ höher als „adobe“.

Jetzt können wir eine Frage stellen: Wie sortiere ich die Wörter im Wörterbuch?

Zum Beispiel haben wir jetzt die folgenden Wörter:

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

Wie sortieren wir es? Hier können wir die Radix-Sortierung verwenden. Das Prinzip der Radix-Sortierung besteht darin, dass wir ein Element in hohe und unterteilen Ein einzelnes Individuum wie Adobe wird in A, d, o, b, e unterteilt, und der Algorithmus wird in A, l, g, o, r, i, t, h, m und dann in we unterteilt vergleiche sie der Reihe nach von rechts nach links, das ist Can. Aber Adobe und Algorithmus können hier nicht direkt verglichen werden, da sie unterschiedlich lang sind. Daher sollten wir vor dem Vergleich die Länge des längsten Elements ermitteln und dann die verbleibenden kurzen Elemente auf die gleiche Länge vervollständigen:

Adobe0000

Algorithmus

Auf diese Weise kann ein Vergleich von rechts nach links gebildet werden: 0:m,0:h,0:t,0:i,e:r,b:o,o : g,d:l,A:A, wir können Adobe> vergleichen

Wenn Sie den folgenden Bildern folgen, wird das Prinzip klarer:

Von We Aus der obigen Abbildung ist ersichtlich, dass die Basissortierung von rechts nach links verglichen wird (das heißt, sie muss in unserer Programmimplementierung viele Male durchlaufen werden), und die spezifische Anzahl der Durchläufe hängt davon ab, wie lang das längste Element von rechts ist Um die Elemente jedes Bits auf der linken Seite zu vergleichen, kann die Bucket-Sortierung oder Zählsortierung verwendet werden. Unter der Annahme, dass die maximale Elementlänge K ist, beträgt die Zeitkomplexität der Basissortierung ist O(n).(k * n) und k ist im Allgemeinen nicht sehr groß und kann als Konstante betrachtet werden, sodass die zeitliche Komplexität der Basissortierung ebenfalls O(n) ist.

Das Folgende ist meine Java-Implementierung:

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;
    }
}

Was zu beachten ist, ist, dass Sie vor dem Sortieren die maximale Elementlänge ermitteln müssen, um die Anzahl der Schleifen zu bestimmen und kürzere Elemente basierend darauf zu vervollständigen die maximale Elementlänge.

Ergebnis der Programmausführung:

Das obige ist der detaillierte Inhalt vonCodebeispiel für die Java-Implementierung der Radix-Sortierung (RadixSort). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!