선형 시간 정렬 - 계수 정렬, 기수 정렬, 통 정렬

이전에 정리 한 것 은 모두 비교 방법 을 통 해 정렬 하 는 알고리즘 이다. 우 리 는 비교 정렬 알고리즘 을 통 해 평균 시간 복잡 도가 O (lgN) 라 는 것 을 알 고 있다.
이 글 은 비교 되 지 않 는 선형 시간 정렬 방법, 계수 정렬, 기수 정렬, 통 정렬 을 분석 해 보 자.
1: 계수 정렬
이름 과 같이 계수 정렬 은 정렬 할 요소 가 이 요소 와 같은 횟수 보다 적 음 을 계산 한 다음 에 이 속성 을 이용 하여 요 소 를 횟수 를 기준 으로 다른 배열 로 옮 기 고 제자리 에서 옮 기지 못 하면 정렬 된 결 과 를 얻 을 수 있 습 니 다.
코드 는 다음 과 같 습 니 다:

void counting_sort(int* arr, int* result, const int size, const int k)
{
    int i = 0;  
    vector count(k+1, 0); 
    
    for(i=0; i=0; --i){
        result[count[arr[i]]-1] = arr[i];   //    -1
        --count[arr[i]];
    }   
}

시간 복잡 도 는 O (n), 공간 복잡 도, O (n + k) 이다.
주의:
> > > 1. 계수 정렬 은 모두 두 개의 추가 배열 을 사 용 했 습 니 다.결 과 를 저장 하 는 데 사용 되 는 result 배열result 배열 은 결 과 를 저장 하 는 데 사 용 됩 니 다. 자 연 스 럽 게 크기 는 원래 배열 arr 의 크기 와 완전히 일치 합 니 다.한편, count 배열 은 모든 요소 에 대해 계산 하 는 것 을 사용 합 니 다. 아래 표 지 는 원래 배열 의 요소 이기 때문에 크기 는 원래 배열 의 최대 값 에 의 해 결정 되 고 크기 는 최대 치 max + 1 입 니 다. 여기 서 우 리 는 외부 매개 변 수 를 통 해 들 어 갑 니 다. 이것 이 바로 k 입 니 다.이렇게 하 는 것 은 그것 이 최대 치 를 지원 하 는 계산 이 필요 하기 때문이다.
> > > 2. 매번 계산 하기 전에 초기 화 해 야 합 니 다. 이것 은 모든 counter 가 공동으로 따 르 는 특징 입 니 다.위 코드 에서 vector 가 초기 화 되 었 습 니 다.
> > > 3. 모든 원 배열 요소 에 대해 서 는 현재 count 배열 의 아래 표 시 됩 니 다. 그래서 count [arr [i] 는 나타 난 횟수 를 표시 합 니 다. 반복 적 으로 나타 날 수 있 습 니 다.
> > > 4. 우 리 는 count 배열 의 내용 을 하나하나 누적 해 야 합 니 다. 현재 좌표 마다 대응 하 는 값 은 좌표 (원래 배열 값) 와 같은 요소 수 를 표시 합 니 다.
> > > 5. 거꾸로 for 순환 은
정렬 의 안정성 을 확보 하 다.우 리 는 거꾸로 돌아 가 count [arr [i] 를 1 로 줄 일 것 입 니 다. 바로 뒤에 arr [i] 가 1 을 줄 이지 않 은 count 값 에 대응 하기 때문에 뒤의 요 소 는 count 값 대회 가 뒤에 놓 여 있 습 니 다.
>>>6.
result 에 부여 할 때 아래 표 시 는 1 을 줄 여야 합 니 다. count 배열 의 요소 의 최소 값 은 1 이기 때문에 어떤 arr [i] 요소 가 count 에 0 번 나 올 수 없습니다. result 의 아래 표 시 는 최소 값 이 0 이기 때문에 1 을 줄 여야 합 니 다. 그렇지 않 으 면 경 계 를 넘 을 수 있 습 니 다.
테스트 파일:

int main()
{
    int array[] = {3, 9, 12, 7, 6, 15, 4, 3, 2, 1}; 
    int len = sizeof(array) / sizeof(len);
    int result[len];
    std::fill(result, result+len, 0); 
    counting_sort(array, result, len, 15);
    for(auto i : result)
        cout<

2: 기수 정렬
기본 사상:
정렬 을 기다 리 는 배열 의 키 워드 를 순서대로 통 으로 나 눕 니 다. 예 를 들 어 세 자리 수 를 정렬 할 때, 우 리 는 먼저 10 개의 통 을 나 누 어 각각 0 ~ 9 의 숫자 를 담 습 니 다. 우 리 는 먼저 한 자리 씩 모든 숫자 를 해당 하 는 통 에 넣 고, 그 다음 에 통 순 으로 0 ~ 9 를 나 누 어 출력 합 니 다. 그리고 열 자리 로 그들 을 다시 통 에 넣 고, 통 순 으로 다시 출력 합 니 다. 여러 번 반복 하면 질서 있 는 배열 을 얻 을 수 있 습 니 다.
우 리 는 대기 열 배열 을 이용 하여 기수 정렬 의 통 집합 을 쉽게 실현 할 수 있 습 니 다. push 가 들 어 갈 때마다 통 아래 에 pop 에 표시 하고 반복 작업 을 하면 정렬 이 완 료 됩 니 다.
한 문 제 를 보다.
int 배열 에 대해 서 는 기수 정렬 알고리즘 을 만 들 고 배열 요 소 를 정렬 하 십시오.
int 배열 A 와 배열 의 크기 n 을 지정 합 니 다. 정렬 된 배열 을 되 돌려 주 십시오. 요소 가 2000 보다 작 음 을 보증 합 니 다.
테스트 샘플:

[1,2,3,5,2,3],6

[1,2,2,3,3,5]

코드 는 다음 과 같 습 니 다:
4. 567913. 그의 시간 복잡 도 는 O (d (n + radix) 이 고 radix 는 기수 이다. 그 중에서 한 번 의 분배 시간 복잡 도 는 O (n) 이 고 한 번 의 수집 시간 복잡 도 는 O (radix) 이 며 모두 d 번 의 분배 와 수집 을 한다. 공간 효율: O (rd + n) 는 약 O (n) 와 같다.
안정성: 안정.
통 정렬
만약 길이 가 N 인 대기 키워드 서열 K [1... n] 이 있다 고 가정 합 니 다. 먼저 이 서열 을 M 개의 하위 구간 (통) 으로 나 누 었 습 니 다. 그 다음 에 특정한 맵 함 수 를 바탕 으로 대기 서열 의 키워드 k 를 i 번 째 통 (즉, 통 배열 B 의 아래 표 i) 에 투사 하면 이 키워드 k 는 B [i] 의 요소 (각 통 B [i] 는 하나의 크기 가 N / M 인 서열) 로 합 니 다. 이 어 각 통 B [i]]모든 요 소 를 비교 정렬 합 니 다 (빠 른 배열 을 사용 할 수 있 습 니 다). 그리고 B [0]. B [M] 의 모든 내용 을 순서대로 출력 합 니 다.
정렬 대기 열 K = {49, 38, 35, 97, 76, 73, 27, 49}. 이 데 이 터 는 모두 1 - 100 사이 입 니 다. 따라서 우 리 는 10 개의 통 을 맞 춘 다음 맵 함수 f (k) = k / 10 을 확인 합 니 다. 첫 번 째 키 워드 는 49 번 째 통 (49 / 10 = 4) 으로 정 해 집 니 다. 순서대로 모든 키 워드 를 통 에 쌓 고 비 어 있 는 통 마다 빠르게 정렬 합 니 다.
통 정렬 은 일종 의 실현 이 아니 라 하나의 사상 이 라 고 할 수 있다. 예 를 들 어 기수 정렬 은 bucket 을 사용 한 것 이 고 나 는 그것 도 통 정렬 이 라 고 할 수 있다 고 생각한다.