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

Java를 사용하여 기수 정렬 알고리즘을 구현하는 방법은 무엇입니까?

기수 정렬 알고리즘은 요소의 비트 값을 기준으로 정렬하는 비비교 정렬 알고리즘입니다. 핵심 아이디어는 단위, 십, 백 및 기타 숫자에 따라 정렬할 숫자를 그룹화한 다음 각 숫자를 차례로 정렬하여 최종적으로 정렬된 시퀀스를 얻는 것입니다. 다음에서는 Java를 사용하여 기수 정렬 알고리즘을 구현하는 방법을 자세히 소개하고 코드 예제를 제공합니다.

우선 기수 정렬 알고리즘에서는 정렬할 숫자를 저장하기 위해 2차원 배열을 준비해야 합니다. 배열의 행 수는 자릿수에 따라 결정됩니다. 예를 들어 정렬할 최대 숫자 수가 n이면 배열의 행 수는 log(n) + 1입니다. 각 열은 해당 숫자에 해당하는 숫자를 저장하는 데 사용됩니다.

다음으로 밑의 자릿수를 결정하기 위해 정렬할 숫자 중 최대값을 찾아야 합니다. 이는 전체 배열을 반복하고 최대값을 취함으로써 달성할 수 있습니다.

그런 다음 기수 정렬을 시작하세요. 먼저, 한 자리 숫자에 따라 해당 버킷에 숫자를 할당합니다. 이 단계를 수행하려면 계산 정렬을 사용할 수 있습니다. 구체적인 방법은 크기가 10인 카운팅 배열을 만들고, 정렬할 배열의 숫자를 반복하고, 한 자리 숫자에 따라 해당 버킷에 숫자를 넣은 다음 버킷의 숫자를 정렬하는 것입니다. 정렬이 끝나면 버킷에 있던 숫자를 다시 배열에 넣어서 순서대로 정렬합니다.

다음에는 다시 해당 버킷에 십의 자리에 맞게 숫자를 할당하고, 버킷 안의 숫자를 정렬합니다. 정렬이 끝나면 버킷에 있던 숫자를 다시 배열에 넣어서 다시 정렬합니다.

모든 숫자가 할당되고 정렬될 때까지 위 단계를 반복하세요. 마지막으로 정렬할 배열의 숫자가 정렬됩니다.

다음은 Java를 사용하여 기수 정렬을 구현하는 코드 예제입니다.

public class RadixSort {
    public static void radixSort(int[] arr) {
        // 找到待排序数组中的最大值，确定需要进行排序的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
      
        // 计算需要进行排序的位数
        int digit = 1;
        while (max / 10 > 0) {
            max /= 10;
            digit++;
        }
      
        // 创建桶和计数数组
        int[][] bucket = new int[10][arr.length];
        int[] count = new int[10];
      
        // 进行基数排序
        for (int i = 0; i < digit; i++) {
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] / (int) Math.pow(10, i)) % 10;
                bucket[num][count[num]++] = arr[j];
            }
          
            int k = 0;
            for (int j = 0; j < count.length; j++) {
                if (count[j] != 0) {
                    for (int l = 0; l < count[j]; l++) {
                        arr[k++] = bucket[j][l];
                    }
                    count[j] = 0;
                }
            }
        }
    }
  
    public static void main(String[] args) {
        int[] arr = {432, 524, 236, 679, 321, 546, 457};
        radixSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

위는 Java를 사용하여 기수 정렬 알고리즘을 구현하는 방법 및 코드 예제입니다. 기수 정렬 알고리즘은 양의 정수를 정렬하는 데 적합합니다. 음수를 포함하는 배열이나 음수를 정렬하려면 먼저 음수가 아닌 숫자로 변환해야 합니다.

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