계수 정렬 Counting sort

계수 정렬 은 비교 에 기반 하지 않 은 정렬 알고리즘 으로 1954 년 에 Harold H. Seward 가 제시 했다.그것 의 장점 은 일정한 범위 내의 정수 에 대해 정렬 할 때 그 복잡 도 는Ο(n + k) (그 중에서 k 는 정수 범위) 는 모든 비교 정렬 알고리즘 보다 빠르다.
알고리즘 사상 계수 정렬 은 입력 한 데이터 에 대해 추가 적 인 제한 조건 이 있 습 니 다. 1. 입력 한 선형 표 의 요 소 는 유한 편차 집합 S 에 속 합 니 다.2. 입력 한 선형 표 의 길 이 는 n 이 고 | S | = k (집합 S 에서 요소 의 전체 항목 은 k 임 을 나타 내 는 것) 는 k = O (n) 입 니 다.이 두 가지 조건 하에 서 계수 정렬 의 복잡성 은 O (n) 이다.
       계수 정렬 의 기본 사상 은 주어진 입력 시퀀스 의 모든 요소 x 에 대해 이 시퀀스 의 중간 값 이 x 보다 작은 요소 의 개 수 를 확인 하 는 것 이다.이 정보 가 있 으 면 x 를 최종 출력 시퀀스 의 정확 한 위치 에 직접 저장 할 수 있 습 니 다.예 를 들 어 입력 시퀀스 에 17 개의 요소 만 x 의 값 보다 작 으 면 x 는 출력 시퀀스 의 18 번 째 위치 에 직접 저장 할 수 있다.물론 여러 요소 가 같은 값 을 가지 고 있 을 때 우 리 는 이 요 소 를 출력 서열 의 같은 위치 에 놓 을 수 없 기 때문에 상기 방안 은 적당 한 수정 을 해 야 한다.입력 한 선형 표 L 의 길이 가 n, L = L1, L2,.., Ln 이 라 고 가정 합 니 다.선형 표 의 요 소 는 유한 편차 집합 S, | S | = k 에 속 하고 k = O (n), S = {S1, S2,..... k} 에 속 합 니 다.계수 정렬 은 다음 과 같다. 1. 전체 집합 S 를 스 캔 하고 모든 Si * 8712 ° S 에 대해 선형 표 L 에서 Si 와 같은 요소 의 개수 T (Si) 를 찾 을 수 있 습 니 다.2. 전체 선형 표 L 을 스 캔 하고 L 의 모든 요소 Li 를 출력 선형 표 의 T (Li) 위치 에 놓 고 T (Li) 를 1 로 줄인다.
기수 정렬 과 구분 하 십시오. 이것 은 두 개의 서로 다른 정렬 입 니 다.
계산 순 서 를 매 기 는 과정 은 초등학교 에서 반 간 부 를 뽑 는 과정 과 비슷 하 다. 예 를 들 어 어떤 사람 이 10 표, 작가 가 9 표, 그 사람 이 반장 이 고 작 가 는 부반장 이다. 첫 번 째 부분 은 표를 끌 고 투표 하 는 것 이다. 두 번 째 부분 은 당신 의 표 에 따라 구체 적 인 과정 을 보 는 것 이다. 하 나 는 모두 세 개의 배열 이 필요 하 다. 각각 배열 대기 배열, 표 상자 배열, 그리고 통 배열 var unsorted = new int [] 이다.{ 6, 2, 4, 1, 5, 9 };  //대기 배열 var ballot = new int [unsorted. Length];         //투표함 배열 var bucket = new int [unsorted. Length];         //통 배열 은 마지막 으로 통 배열 을 보고 배열 과 표 상자 배열 의 초기 상 태 를 먼저 본다. 교체 변수 i = 0 시 대기 배열 [i] = 6, 표 상자 배열 [i] = 0. 이렇게 교체 변 수 를 통 해 숫자 와 통 번호 (즉 표) 의 연결 대기 배열 [62, 4, 1, 5 9] i = 0 시 대기 배열 에서 6 표 상자 배열 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 을 추출 할 수 있다.동시에 투표함 배열 에서 6 의 표 0, 즉 통 번 호 를 꺼 낼 수 있다.
득 표 과정
먼저 6 열 에서 표를 끌 기 시 작 했 습 니 다. 6 의 표 상 자 는 0 번 입 니 다. 6 은 다른 모든 숫자 에 대해 나 보다 어 리 거나 나 와 같은 사람 이 있 으 면 투 표를 해 주세요. 그렇지 않 으 면 때 리 겠 습 니 다. 그래서 2, 4, 15 는 각각 6 에 게 투 표를 하고 0 번 표 상 자 를 넣 습 니 다. 6 은 4 표 대기 배열 [6, 2, 4, 1, 5] 표 배열 [40, 00, 0]
다음 2 부터 표를 끌 기 시 작 했 습 니 다. 다른 사람 에 게 누가 나 보다 어 리 고 누가 나 에 게 표를 던 졌 습 니까? 그렇지 않 으 면 당신 을 만 들 었 습 니 다. 그래서 1 표를 던 졌 습 니 다. 다른 사람 은 2 보다 크 고 상대 하지 않 았 습 니 다. 당신 이 정말 2 라 고 생각 했 습 니 다.
그 러 자 2 는 1 표 에서 대기 배열 을 받 았 다. [6, 2, 4, 1, 5, 9] 박스 배열 [4, 1, 0, 0]
그리고 그 다음은...
4. 2 와 1 의 투 표를 받 아 총 2 표, 1 은 0 표를 얻 었 다. 아무 도 그 에 게 투표 하지 않 았 다. 5 는 2, 4, 1 은 3 표를 얻 었 다. 9 는 모든 사람 (자신 제외) 의 투 표를 받 았 고 총 5 표 (배열 길이 - 1 표) 의 투 표를 마 쳤 을 때 상 태 는 이렇게 배열 되 어 있 었 다. [6, 2, 4, 1, 5 9] 박스 배열 [4, 1, 2, 0, 3, 5]
입 통 과정
투표 과정 이 끝나 면 모든 사람 이 자신의 표 수 를 가지 고 있다.[0 1 2 3 4 5] / / 안에 있 는 숫자 는 통 번호 가 통 에 들 어간 후 [1 2 4 5 6 9] / 1 은 0 표, 들 어간 0 번 통 의 정렬 이 끝나 면 순서대로 출력 하면 된다. [1 2 4 5 6 9] 숫자 가 클 수록 표 가 많 고 9 는 자신 을 제외 한 모든 사람의 표, 5 표, 표 가 가장 많 기 때문에 9 가 가장 크 고 한 사람 이 가장 많이 가지 고 있다.표 한 장 에 1 표 가 가장 적 기 때문에 1 은 가장 작은 숫자 입 니 다. 계산 순 서 는 통 배열 의 효율 과 빠 른 배열 의 패 도 를 동시에 가지 고 있 습 니 다. 완성 코드 는 다음 과 같 습 니 다.

#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range
int a[MAXN], c[MAXN], ranked[MAXN];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; 
        ++c[a[i]];
    }
    for (int i = 1; i < k; ++i)
        c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i)
        ranked[--c[a[i]]] = a[i];
    for (int i = 0; i < n; ++i)
        cout << ranked[i] << endl;
    return 0;
}