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

C++에서 카운팅 정렬 알고리즘을 사용하는 방법

카운팅 정렬 알고리즘은 비교적 간단하고 효율적인 정렬 알고리즘으로 정수 시퀀스가 ​​정렬되는 시나리오에 적합합니다. 기본 아이디어는 각 요소 이전의 요소 수가 자신보다 작는지 확인하여 정렬된 배열에서 해당 요소의 위치를 ​​결정하는 것입니다.

카운팅 정렬 알고리즘의 단계는 다음과 같습니다.

1. 정렬할 배열에서 최대값을 찾아 카운팅 배열의 길이를 결정합니다.
2. 최대값에 1을 더한 길이의 카운트 배열을 생성하고 0으로 초기화합니다.
3. 정렬할 배열을 순회하며 각 요소의 발생 횟수를 세어 통계 결과를 카운트 배열에 저장합니다.
4. 각 위치의 값이 이전 위치 값의 합과 같도록 카운트 배열을 변환합니다.
5. 정렬할 배열과 길이가 같은 임시 배열을 만들어 정렬 결과를 저장하세요.
6. 정렬할 배열을 뒤에서 앞으로 탐색하고, 개수 배열을 기준으로 정렬 결과에서 각 요소의 위치를 ​​결정하고, 요소를 임시 배열에 저장합니다.
7. 임시 배열의 결과를 다시 정렬할 배열에 복사하면 정렬이 완료됩니다.

다음은 C++ 언어로 구현된 카운팅 정렬 알고리즘의 예제 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

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

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

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

위 코드에서는 보조 카운팅 배열을 사용하여 각 요소의 발생 횟수를 계산한 후 발생 횟수를 계산합니다. 변형을 통해 각 요소의 위치를 ​​정렬한 결과입니다. 마지막으로 정렬된 결과를 원래 배열에 다시 복사합니다.

위의 예제 코드를 통해 카운팅 정렬 알고리즘의 구현 과정을 볼 수 있습니다. 시간 복잡도는 O(n+k)입니다. 여기서 n은 정렬할 시퀀스의 길이이고 k는 그 합입니다. 최대 요소 값과 최소 요소 값의 차이는 1입니다.

요약하자면, 카운팅 정렬 알고리즘은 정수 시퀀스가 ​​정렬되는 시나리오에 적합한 간단하면서도 효율적인 정렬 알고리즘입니다. 적절한 데이터 구조와 알고리즘을 사용하면 정렬 작업을 더 잘 수행할 수 있습니다.

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