계수 정렬, 통 정렬 과 기수 정렬

계수 정렬
입력 한 요소 가 n 개 0 에서 k 사이 의 정수 일 때 실행 시간 은?Θ(n + k)。계수 정렬 은 비교 정렬 이 아니 라 정렬 속도 가 모든 비교 정렬 알고리즘 보다 빠르다.
계산 에 사용 되 는 배열 C 의 길 이 는 정렬 대기 배열 의 데이터 범위 (정렬 대기 배열 의 최대 값 과 최소 값 의 차이 에 1 을 더 하 는 것 과 같 음) 에 달 려 있 기 때문에 계산 정렬 은 데이터 범위 가 큰 배열 에 많은 시간 과 메모리 가 필요 합 니 다.예 를 들 어 계수 정렬 은 0 에서 100 사이 의 숫자 를 정렬 하 는 가장 좋 은 알고리즘 이지 만 알파벳 순 으로 사람의 이름 을 정렬 하 는 데 적합 하지 않다.그러나 계수 정렬 은 기수 정렬 에 있 는 알고리즘 으로 데이터 범위 가 큰 배열 을 정렬 할 수 있다.
알고리즘 의 절 차 는 다음 과 같다.
정렬 할 배열 의 최대 와 최소 요 소 를 찾 아 라 배열 의 모든 값 이 i 인 요소 가 나타 나 는 횟수 를 통계 하고 배열 C 의 i 항 에 저장 합 니 다.
모든 계수 누적 (C 의 첫 번 째 요소 부터 각 항목 과 이전 항목 을 추가) 역방향 으로 대상 배열 을 채 웁 니 다: 모든 요소 i 를 새 배열 의 C (i) 항목 에 두 고 하나의 요 소 를 넣 을 때마다 C (i) 를 1 에서 빼 냅 니 다.
코드 붙 이기:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//          ，   0-99
#define	NUM_RANGE (100)

void print_arr(int *arr, int n)
{
       int i;
       for(i=0; i<n; i++){
               if(!i){
                       printf("%d", arr[i]);
               }else{
                       printf(" %d", arr[i]);
               }
       }
       printf("
");
}

/*
       ：
	1.                 
	2.         i        ，    C  i 
	3.        （ C         ，         ）
	4.        ：     i       C(i) ，        C(i)  1
*/

void counting_sort(int *ini_arr, int *sorted_arr, int n)
{
       int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);
       int i, j, k;

	   //     ，         
       for(k=0; k<NUM_RANGE; k++){
               count_arr[k] = 0;
       }
       
	   for(i=0; i<n; i++){
               count_arr[ini_arr[i]]++;
       }


       for(k=1; k<NUM_RANGE; k++){
               count_arr[k] += count_arr[k-1];
       }

       for(j=n-1 ; j>=0; j--){
		   int elem = ini_arr[j];
		   int index = count_arr[elem]-1;
           sorted_arr[index] = elem;
           count_arr[elem]--;
       }
       free(count_arr);
}


int main(int argc, char* argv[])
{
       int n;
       if(argc < 2){
               n = 10;
       }else{
               n = atoi(argv[1]);
       }
       int i;
       int *arr = (int *)malloc(sizeof(int) * n);
       int *sorted_arr = (int *)malloc(sizeof(int) *n);
       srand(time(0));

	   
       for(i=0; i<n; i++){
               arr[i] = rand() % NUM_RANGE;
       }

       printf("ini_array: ");
       print_arr(arr, n);
       counting_sort(arr, sorted_arr, n);
       printf("sorted_array: ");
       print_arr(sorted_arr, n);
       free(arr);
       free(sorted_arr);
	   return 0;
}

 통 정렬:http://blog.sina.com.cn/s/blog_667739ba0100veth.html
통 정렬 의 기본 사상
길이 가 N 인 대기 키워드 시퀀스 K [1... n] 가 있다 고 가정 합 니 다.우선 이 서열 을 M 개의 하위 구간 (통) 으로 나눈다.그 다음 에 특정한 매 핑 함 수 를 바탕 으로 배열 되 어 있 는 키워드 k 를 i 번 째 통 에 매 핑 합 니 다 (즉, 통 배열 B 의 아래 표 시 된 i). 그러면 이 키 워드 는 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).순서대로 모든 키 워드 를 통 에 쌓 고 빈 통 마다 빠르게 정렬 합 니 다.
통 정렬 대가 분석
통 정렬 은 함수 의 매 핑 관 계 를 이용 하여 거의 모든 비교 작업 을 감소 시 켰 다.실제로 통 정렬 의 f (k) 값 의 계산 은 그 역할 은 빠 른 배열 에서 구분 하 는 것 과 같 고 대량의 데 이 터 를 기본 적 이 고 질서 있 는 데이터 블록 (통) 으로 나 누 었 다.그리고 통 에 있 는 소량의 데 이 터 를 선진 적 인 비교 정렬 만 하면 된다.
 
N 개의 키 워드 를 통 으로 정렬 하 는 시간 복잡 도 는 두 부분 으로 나 뉜 다.
(1) 모든 키 워드 를 반복 적 으로 계산 하 는 통 맵 함수 입 니 다. 이 시간 복잡 도 는 O (N) 입 니 다.
(2) 선진 적 인 비교 정렬 알고리즘 을 이용 하여 각 통 안의 모든 데 이 터 를 정렬 하고 그 시간 복잡 도 는 ∑ O (Ni * logNi) 이다.그 중에서 Ni 는 제 i 통 의 데이터 양 이다.
 
두 번 째 부분 은 통 의 정렬 성능 의 좋 고 나 쁨 을 결정 하 는 요소 임 이 분명 하 다.통 내 데이터 의 수량 을 최대한 줄 이 는 것 이 효율 을 높이 는 유일한 방법 이다.따라서 우 리 는 가능 한 한 다음 두 가 지 를 해 야 한다.
(1) 매 핑 함수 f (k) 는 N 개의 데 이 터 를 M 개의 통 에 평균 적 으로 배분 할 수 있 습 니 다. 그러면 각 통 에 [N / M] 개의 데이터 양 이 있 습 니 다.
(2) 가능 한 한 통 의 수량 을 늘린다.극한 상황 에서 모든 통 은 하나의 데이터 만 얻 을 수 있 기 때문에 통 안의 데이터 의 '비교' 정렬 작업 을 완전히 피 할 수 있다.물론 이 점 을 실현 하 는 것 은 쉽 지 않다. 데이터 의 양 이 많은 상황 에서 f (k) 함 수 는 통 의 집합 수량 이 많 고 공간 낭비 가 심각 하 다.이것 이 바로 시간 대가 와 공간 대가 의 저울질 문제 다.
 
N 개의 대기 데이터 에 대해 M 개의 통, 평균 배럴 [N / M] 개의 데이터 의 통 정렬 평균 시간 복잡 도 는 다음 과 같다.
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
N = M 일 때, 즉 극한 상황 에서 통 마다 데이터 가 하나 밖 에 없 을 때.통 정렬 의 가장 좋 은 효율 은 O (N) 에 도달 할 수 있다.
 
요약: 통 정렬 의 평균 시간 복잡 도 는 선형 O (N + C) 이 고 그 중에서 C = N * (logN - logM) 이다.같은 N 에 비해 통 수량 M 이 많 을 수록 효율 이 높 고 가장 좋 은 시간 복잡 도 는 O (N) 에 이른다.물론 통 정렬 의 공간 복잡 도 는 O (N + M) 로 입력 데이터 가 매우 크 고 통 의 수량 도 매우 많 으 면 공간 대 가 는 의심 할 여지없이 비싸다.이 밖 에 통 의 순 서 는 안정 적 이다.
저 는 개인 적 으로 또 하나의 느낌 이 있 습 니 다. 알고리즘 을 찾 을 때 비교 알고리즘 을 바탕 으로 하 는 가장 좋 은 시간 복잡 도 역시 O (logN) 입 니 다.예 를 들 어 반 으로 접어 서 찾기, 균형 이 잡 힌 이 진 트 리, 붉 은 검 은 나무 등 이다.그러나 Hash 표 는 O (C) 선형 단계 의 검색 효율 (충돌 하지 않 는 상황 에서 검색 효율 이 O (1) 에 달 합 니 다.여러분 잘 체험 해 보 세 요. Hash 표 의 사상 과 통 의 순 서 는 같은 작업 의 묘 미 를 가지 고 있 지 않 습 니까?
기수 정렬
위의 문 제 는 다 중 키워드 의 정렬 이지 만 단일 키워드 도 이런 방식 을 사용 할 수 있다.
예 를 들 어 문자열 'abcd', 'aesc', 'dwsc', 'rews' 는 모든 문 자 를 하나의 키워드 로 볼 수 있다.또한 정수 425, 321, 235, 432 도 각 자리 의 숫자 를 하나의 키워드 로 할 수 있다.
 
기수 정렬 의 사상 은 대기 데이터 중의 각 그룹의 키 워드 를 순서대로 통 으로 분배 하 는 것 이다.예 를 들 어 아래 의 대기 서열:
278、109、063、930、589、184、505、269、008、083
우 리 는 각 수치의 개 위, 10 위, 백 위 를 세 개의 키워드 로 나눈다. 278 - > k1 (개 위) = 8, k2 (10 위) = 7, k3 = (백 위) = 2.
그 다음 에 가장 낮은 비트 부터 (첫 번 째 키워드 부터) 모든 데이터 의 k1 키 워드 를 통 으로 분배 합 니 다 (모든 숫자 가 0 - 9 이기 때문에 통 크기 는 10 입 니 다). 그리고 통 의 데 이 터 를 순서대로 출력 하여 아래 의 순 서 를 얻 습 니 다.
930、063、083、184、505、278、008、109、589、269
그 다음 에 위의 서열 에 대해 k2 통 에 대한 분 배 를 실시 하고 출력 서열 은 다음 과 같다.
505、008、109、930、063、269、278、083、184、589
마지막 으로 k3 통 에 대한 배분, 출력 순 서 는 다음 과 같 습 니 다.
008、063、083、109、184、269、278、505、589、930
 
성능 분석
기수 정렬 의 성능 이 통 정렬 보다 약간 떨 어 지 는 것 이 분명 하 다.매번 키워드 의 통 분 배 는 O (N) 의 시간 복잡 도 를 필요 로 하고 분 배 된 후에 새로운 키워드 서열 을 얻 으 려 면 O (N) 의 시간 복잡 도 를 필요 로 한다.만약 에 대기 데이터 가 d 개의 키워드 로 나 눌 수 있다 면 기수 정렬 의 시간 복잡 도 는 O (d * 2N) 가 될 것 이다. 물론 d 는 N 보다 훨씬 작 아야 하기 때문에 기본적으로 선형 등급 이다.기수 정렬 의 공간 복잡 도 는 O (N + M) 이 고 그 중에서 M 은 통 의 수량 이다.일반적으로 N > > M 이 므 로 추가 공간 은 약 N 개 정도 필요 합 니 다.
 
그러나 통 정렬 에 비해 기수 정렬 에 필요 한 통 의 수량 은 많 지 않다.또한 기수 정렬 은 '비교' 작업 이 거의 필요 하지 않 고 통 정렬 은 통 이 상대 적 으로 적은 상황 에서 통 안의 여러 데 이 터 는 비교 작업 을 바탕 으로 정렬 해 야 한다.따라서 실제 응용 에서 기수 정렬 의 응용 범 위 는 더욱 광범 위 하 다.