계수 정렬 (계수 정렬)

위 키http://en.wikipedia.org/wiki/Counting_sort http://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F
계수 정렬 (Counting sort) 은 안정 적 인 정렬 알고리즘 이다.계수 정렬 은 추가 배열 C 를 사용 합 니 다. 그 중에서 i 번 째 요 소 는 정렬 대기 배열 A 의 중간 값 이 i 와 같은 요소 의 개수 입 니 다.그리고 배열 C 에 따라 A 의 요 소 를 정확 한 위치 로 배열 합 니 다.
계수 정렬 의 특징
입력 한 요소 가 n 개 0 에서 k 사이 의 정수 일 때 실행 시간 은?Θ(n + k)。계수 정렬 은 비교 정렬 이 아니 라 정렬 속도 가 모든 비교 정렬 알고리즘 보다 빠르다.
계산 에 사용 되 는 배열 C 의 길 이 는 정렬 대기 배열 의 데이터 범위 (정렬 대기 배열 의 최대 값 과 최소 값 의 차이 에 1 을 더 하 는 것 과 같 음) 에 달 려 있 기 때문에 계산 정렬 은 데이터 범위 가 큰 배열 에 많은 시간 과 메모리 가 필요 합 니 다.예 를 들 어 계수 정렬 은 0 에서 100 사이 의 숫자 를 정렬 하 는 가장 좋 은 알고리즘 이지 만 알파벳 순 으로 사람의 이름 을 정렬 하 는 데 적합 하지 않다.그러나 계수 정렬 은 기수 정렬 에 있 는 알고리즘 으로 데이터 범위 가 큰 배열 을 정렬 할 수 있다.
알고리즘 의 절 차 는 다음 과 같다.

정렬 할 배열 의 최대 와 최소 요 소 를 찾 아 라

배열 의 모든 값 이 i 인 요소 가 나타 난 횟수 를 통계 하고 배열 C 의 i 항

에 저장 합 니 다.

모든 계수 누적 (C 의 첫 번 째 요소 부터 모든 항목 과 이전 항목 을 추가) (그 요소 의 개 수 를 기록 하여 전체 에서 의 순 위 를 계산 합 니 다)

대상 배열 을 역방향 으로 채 웁 니 다. 모든 요소 i 를 새 배열 의 C (i) 항목 에 두 고 하나의 요 소 를 넣 을 때마다 C (i) 를 1

에서 빼 냅 니 다.
In pseudocode, this may be expressed as follows:

''' calculate histogram: '''
# allocate an array Count[0..k] ; THEN
# initialize each array cell to zero ; THEN
for each input item x:
    increment Count[key(x)]
 
''' calculate starting index for each key: '''
total = 0
for i = 0, 1, ... k:
    oldCount = Count[i]
    Count[i] = total
    total = total + oldCount
 
''' copy inputs into output array in order: '''
# allocate an output array Output[0..n-1] ; THEN
for each input item x:
    Output[Count[key(x)]] = x
    decrement Count[key(x)]
return Output
  
After the first for loop,  Count[i]  stores the number of items with key equal to  i .After the second for loop, it instead stores the number of items with key less than  i , which is the same as the first index at which an item with key i  should be stored in the output array. Throughout the third loop, Count[i]  always stores the next position in the output array into which an item with key  i  should be stored, so each item is moved into its correct position in the output array. The relative order of items with equal keys is preserved here; i.e., this is a stable sort. 
내 가 쓴 코드: (최신 수정 2013 - 12 - 12)
/*
 *     ：      
 * huntinux
 * 13-12-12
 *
 */

#include <stdio.h>
#include <malloc.h>

int find_max(int *a, int n)
{
	int i;
	int max = a[0];

	for(i = 1; i < n; i++){
		if(a[i]>max)
			max = a[i];
	}
	return max;
}

void counting_sort(int *a, int n)
{
    int *count, *tmparr;
    int i;
    int size;

    size = find_max(a,n); //       	
    size += 1; //      0  ，        。
    size = size > n ? size : n; //                       。

    count = malloc(sizeof(int) * size );
    if(!count)
        perror("malloc");
    for(i = 0; i < size; i++)
        count[i] = 0;
    
    for(i = 0; i < n; i++)
        count[a[i]]++;

    for(i = 1; i < size; i++)
        count[i] += count[i-1];

    tmparr = malloc(sizeof(int) * n);
    if(!tmparr)
        perror("malloc");
    for(i = 0; i < n; i++)
        tmparr[i] = 0;

    for(i = n-1; i >= 0; i--) //   i n-1  ，            ，            。（      ）
        tmparr[--count[a[i]]] = a[i];

    for(i = 0; i < n; i++)
        a[i] = tmparr[i];

    free(count);
    free(tmparr);
}

void print_arr(int *a, int n, char *msg)
{
    int i;
    
    if(msg)
        printf("%s
", msg);

    for(i = 0; i < n; i++)
        printf("%d\t", a[i]);
    printf("
");

}


int main()
{
    int a[15] = {8, 4 , 2, 6, 3, 1, 9, 3, 5, 7, 1, 100, 0, 2, 5};

    print_arr(a, 15, "before sorting:");
    counting_sort(a, 15);
    print_arr(a, 15, "after sorting:");

    return 0;
}
  
아래 코드 는 안정 적 인 정렬 을 확보 하 는 관건 입 니 다.
for(i = n-1; i >= 0; i--) //   i n-1  ，            ，            。（      ）
		tmparr[--count[a[i]]] = a[i];