기수 정렬(RadixSort)의 Java 구현 코드 예

이 기사의 내용은 Java에서 기수 정렬(RadixSort)을 구현하기 위한 코드 예제에 대한 것입니다. 필요한 친구가 참고할 수 있기를 바랍니다.

기수 정렬은 버킷 정렬과 계산 정렬의 파생형입니다. 기수 정렬에는 이 두 가지 유형 중 하나가 사용되기 때문입니다.

기수 정렬로 정렬할 요소는 높은 숫자와 낮은 숫자가 있어야 합니다. 예를 들어 adobe, activiti, activiti라는 단어는 adobe보다 높습니다.

이제 질문을 할 수 있습니다. 사전에서 단어를 정렬하는 방법은 무엇인가요?

예를 들어 다음 단어가 있습니다:

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

어떻게 정렬합니까? 여기서 기수 정렬을 사용할 수 있습니다. 기수 정렬의 원리는 요소를 높은 비트와 낮은 비트에 따라 개별 개체로 나누는 것입니다. 예를 들어 Adobe를 A, d, o, b, e로 나누고, 알고리즘을 A, l, g, o, r, i, t, h, m으로 나눈 다음 오른쪽에서 왼쪽으로 순차적으로 비교합니다. . 하지만 Adobe와 알고리즘은 길이가 다르기 때문에 여기에서 직접 비교할 수 없습니다. 따라서 비교하기 전에 가장 긴 요소의 길이를 찾은 다음 나머지 짧은 요소를 동일한 길이로 완성해야 합니다.

Adobe0000

Algorithm

In 이렇게 하면 오른쪽에서 왼쪽으로 0:m,0:h,0:t,0:i,e:r,b:o,o:g,d:l,A:A로 비교가 이루어집니다. Adobe > Algorihtm

과 비교할 수 있습니다. 다음 그림을 보면 원리가 더 명확해집니다.

위 그림에서 기수 정렬이 오른쪽에서 왼쪽으로 비교되는 것을 볼 수 있습니다. 우리 프로그램 구현에서 여러 번 탐색해야 하며, 탐색해야 하는 특정 횟수는 가장 긴 요소의 길이에 따라 달라집니다. 버킷 정렬 또는 카운팅 정렬을 사용하여 각 비트의 요소를 오른쪽에서 왼쪽으로 비교할 수 있습니다. 버킷 정렬과 카운팅 정렬의 시간 복잡도는 모두 O(n)이며, 기수 정렬의 시간 복잡도는 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;
    }
}

주의해야 할 점은 정렬하기 전에 최대 요소 길이를 찾아 루프 수를 결정하고 최대 요소 길이를 기반으로 더 짧은 요소를 완성해야 한다는 것입니다.

프로그램 실행 결과:

위 내용은 기수 정렬(RadixSort)의 Java 구현 코드 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!