Java를 사용하여 계산 정렬 알고리즘을 구현하는 방법

Java를 사용하여 계산 정렬 알고리즘을 구현하는 방법

계산 정렬은 각 요소가 배열에 나타나는 횟수를 계산한 다음 해당 요소를 올바른 위치에 배치하는 것입니다. 위치는 나타나는 횟수에 따라 결정됩니다. 카운팅 정렬의 시간 복잡도는 O(n+k)입니다. 여기서 n은 정렬할 시퀀스의 길이이고 k는 정렬할 시퀀스에서 가장 큰 요소의 범위입니다.

Java에서는 다음 코드 예제를 사용하여 계산 정렬 알고리즘을 구현할 수 있습니다.

public class CountingSort {
    public static void countingSort(int[] array) {
        int n = array.length;
        
        // 找到待排序序列中的最大值
        int max = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 创建一个计数数组，并初始化为0
        int[] count = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            count[i] = 0;
        }
        
        // 统计每个元素在待排序序列中出现的次数
        for (int i = 0; i < n; i++) {
            count[array[i]]++;
        }
        
        // 根据计数数组构建有序序列
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                array[index] = i;
                index++;
                count[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] array = {9, 1, 5, 3, 7, 3, 8, 2, 6};
        
        System.out.println("排序前：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        countingSort(array);
        
        System.out.println("排序后：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

위 코드에서는 먼저 정렬할 시퀀스의 최대값을 찾은 다음 계산 배열을 만들고 숫자를 추가합니다. 각 요소의 발생 횟수 통계는 count 배열에 있습니다. 다음으로, count 배열을 기반으로 정렬된 시퀀스를 구성합니다. 특정 작업은 발생 횟수에 따라 정렬할 시퀀스에 count 배열의 요소를 배치하는 것입니다. 마지막으로 countingSort 메서드를 호출하고 순서가 지정된 시퀀스를 인쇄하면 개수 정렬 결과를 볼 수 있습니다.

계산 정렬에는 정렬할 시퀀스의 요소 범위에 대한 특정 제한이 있으며 음수가 아닌 정수 시퀀스에만 적용 가능하다는 점에 유의해야 합니다. 정렬할 시퀀스에 음수나 다른 데이터 유형의 요소가 있는 경우 계수 정렬 알고리즘을 사용하려면 적절한 처리가 필요합니다.

위 내용은 Java를 사용하여 계산 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!