C++에서 기수 정렬 알고리즘을 사용하는 방법

C++에서 기수 정렬 알고리즘을 사용하는 방법

기수 정렬 알고리즘은 정렬할 요소를 제한된 숫자 집합으로 나누어 정렬을 완료하는 비비교 정렬 알고리즘입니다. C++에서는 기수 정렬 알고리즘을 사용하여 정수 집합을 정렬할 수 있습니다. 아래에서는 특정 코드 예제를 사용하여 기수 정렬 알고리즘을 구현하는 방법을 자세히 설명합니다.

1. 알고리즘 아이디어
   기수 정렬 알고리즘의 아이디어는 정렬할 요소를 제한된 디지털 비트 세트로 나눈 다음 각 비트의 요소를 차례로 정렬하는 것입니다. 각 비트에 대한 정렬이 완료된 후 해당 비트의 순서에 따라 요소를 재구성하고 모든 비트가 정렬될 때까지 다음 비트의 정렬을 계속합니다.
2. 구체적인 구현 단계
   (1) 먼저 정렬할 모든 요소 중 최대값의 자릿수를 결정해야 합니다. 이것은 우리가 수행해야 할 정렬 라운드 수를 결정합니다.

(2) 그런 다음 보조 배열과 개수 배열을 만들어야 합니다. 보조 배열은 정렬 과정에서 임시 결과를 저장하는 데 사용되고, 계수 배열은 각 숫자의 발생 횟수를 기록하는 데 사용됩니다.

(3) 다음으로 여러 차례 정렬을 수행해야 합니다. 각 정렬 라운드는 현재 비트 크기에 따라 배열을 재구성합니다.

(4) 각 정렬 라운드에서는 정렬할 배열을 순회하고 각 요소의 현재 비트 값을 인덱스로 사용하고 요소를 해당 버킷에 넣어야 합니다.

(5) 그런 다음 각 버킷의 요소 수를 계산해야 하며, 이는 계산 배열을 사용하여 기록할 수 있습니다.

(6) 다음으로 배열 수를 세어 보조 배열의 각 버킷에 있는 요소의 위치를 ​​결정해야 합니다. 이는 배열에 있는 요소의 접두어 합계를 계산하여 확인할 수 있습니다.

(7) 마지막으로 보조 배열의 요소를 정렬할 배열에 덮어써서 정렬 라운드를 완료합니다.

(8) 모든 비트가 정렬될 때까지 (3)~(7) 단계를 반복합니다.

3. 코드 예제
   다음은 기수 정렬 알고리즘을 구현하기 위해 C++를 사용하는 코드 예제입니다.

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

        for (int i = 0; i < arr.size(); i++) {
            count[(arr[i] / digit) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

        for (int i = 0; i < arr.size(); i++) {
            arr[i] = temp[i];
        }

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

위 예제 코드에서는 먼저 정렬할 배열의 최대값을 찾아 몇 라운드를 결정하는지 결정합니다. 정렬이 필요합니다. 그런 다음 보조 배열과 개수 배열을 만들었습니다. 다음으로, 현재 비트 크기에 따라 배열을 재조립하기 위해 여러 차례의 정렬을 수행합니다. 마지막으로 정렬된 결과를 출력합니다.

요약:
기수 정렬 알고리즘을 사용하면 C++에서 정수 집합을 정렬할 수 있습니다. 기수 정렬 알고리즘의 핵심 아이디어는 정렬할 요소를 제한된 숫자 비트 집합으로 나눈 다음 각 비트의 요소를 차례로 정렬하는 것입니다. 이 비비교 정렬 알고리즘은 정수 집합의 정렬 문제를 효과적으로 처리할 수 있습니다.

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