계수 정렬의 Java 구현 코드 예(CountingSort)

이 기사는 Java에서 계산 정렬(CountingSort) 구현에 대한 코드 예제를 제공합니다. 여기에는 특정 참조 값이 있으므로 도움이 될 수 있습니다.

카운팅 정렬은 버킷 정렬의 특별한 유형입니다.

n개의 데이터를 정렬할 때 범위가 크지 않으면 최대값 K를 취하여 데이터를 K개의 버킷에 분산시킬 수 있습니다.

각 버킷의 데이터는 동일합니다(이렇게 하면 정렬 시간이 절약됩니다. 버킷)을 선택한 다음 순서대로 꺼내세요.

물론 셈하고 분류하는 것은 말은 간단하지만, 글로 써보면 이해하기 어려운 곳이 있습니다.

예를 들어, 이제 2, 5, 3, 0, 2, 3, 0, 3 등 8개의 숫자가 있습니다. 이를 정렬하려면 먼저 최대값인 5를 구한 다음 0-5 사이의 범위를 결정할 수 있습니다.

각 위치에 해당하는 각 숫자의 개수를 계산하기 위해 0~5의 메모리 공간을 적용합니다.

아래 그림은 메모리 공간 0~5의 데이터를 보여줍니다. 0은 2번 나타나고, 1은 0번 나타나고, 2는 3번 나타나고, 4는 0번 나타납니다.

동시에 몇 가지 규칙을 요약할 수도 있습니다. 예를 들어 이제 c[2]의 위치를 ​​볼 수 있으며 2는 두 번 나타나고 c[0] + c[1에는 총 2개의 요소가 있습니다. ]가 2 앞에 있으므로 c[ 2] 원래 배열에서 이 두 2의 해당 위치는 2와 3입니다. c[2] = c[0] + c[1]의 위치라는 규칙을 그릴 수 있습니다. , 그리고 다음 c[3] = c[ 2] + c[1]의 위치를 ​​다음과 같이 순차적으로 합산합니다. 그런 다음 원본 배열 2, 5, 3, 0, 2, 3, 0을 스캔합니다. 3. 숫자를 만날 때마다 그 숫자를 c로 대체합니다. 배열의 인덱스에서 정렬한 후 현재 요소의 실제 인덱스를 가져옵니다.

내 Java 구현은 다음과 같습니다.

package com.structure.sort;
/**
 * @author zhangxingrui
 * @create 2019-01-30 13:45
 **/
public class CountingSort {
    public static void main(String[] args) {
        int[] numbers = {3, 9, 2, 1, 8, 7, 6, 10, 9};
        // 假设数组中存储的都是非负整数
        countingSort(numbers);
        for (int number : numbers) {
            System.out.println(number);
        }
    }
    /**
     * @Author: xingrui
     * @Description: 计数排序
     * @Date: 13:57 2019/1/30
     */
    private static void countingSort(int[] numbers){
        int n = numbers.length;
        int maxNumber = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] > maxNumber)
                maxNumber = numbers[i];
        }
        int[] r = new int[n];
        int[] c = new int[maxNumber + 1];
        for(int i = 0; i < n; ++i){
            c[numbers[i]]++;
        }
        for(int i = 1; i <= maxNumber; ++i){
            c[i] = c[i-1] + c[i];
        }
        for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;
        }
        for(int i = 0; i < n; ++i){
            numbers[i] = r[i];
        }
    }
}

키 코드:

for (int i = n - 1; i >= 0; --i){
            int index = c[numbers[i]];
            r[index - 1] = numbers[i];
            c[index]--;5         
            }

c 배열에서 정렬된 인덱스를 검색합니다.

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