[데이터 구조] 비교 정렬 알고리즘 (계수 정렬 과 기수 정렬 실현)

● 계수 정렬
1. 알고리즘 사상:
       계수 정렬 은 직접 주소 지정 법의 변형 이다.일정한 크기 의 공간 을 열 어 같은 데이터 가 나타 난 횟수 를 통계 한 다음 에 원래 의 서열 에 다시 쓴다.
2. 절차:
1) 시퀀스 의 최대 와 최소 데 이 터 를 찾 아 열 린 공간 크기 를 확인한다.
2) 공간 을 개척 하고 개 방 된 공간 을 이용 하여 각 데이터 의 개 수 를 저장한다.
3) 정렬 된 서열 을 원래 서열 에 다시 쓴다.
구체 적 인 실현 은 다음 과 같다.

void CountSort(int *arr, int size)
{
 assert(arr);
 int min = arr[0];
 int max = arr[0];
 int num = 0;
 for (int i = 0; i < size; ++i)//        
 {
  if (arr[i] < min)
  {
   min = arr[i];
  }
  if (arr[i] > max)
  {
   max = arr[i];
  }
 }
 num = max - min + 1;//       
 int *count = new int[num];
 memset(count, 0, sizeof(int)*num);//   count
 for (int i = 0; i < size; ++i)
 {
  count[arr[i] - min]++;//    
 }
 int index = 0;
 for (int i = 0; i < num; ++i)
 {
  while (count[i]--)
  {
   arr[index] = i + min;//       
   index++;
  }
 }
}

장단 점:
장점: 일정한 범위 내의 정수 정렬 을 할 때 그 복잡 도 는Ο(n + k) (그 중 k 는 정수 범위), 모든 비교 정렬 알고리즘 보다 빠 릅 니 다.
약점: 기수 정렬 은 대응 하 는 크기 의 공간 을 열 어야 한다. k 가 비교적 클 때 공간 이 용 률 이 높 지 않 기 때문에 데이터 가 비교적 밀집 한 서열 에 적응 해 야 한다.만약 데이터 가 밀집 되 고 중복 되 지 않 는 다 면 우 리 는 비트 맵 으로 실현 할 수 있다.
● 기수 정렬
       기수 정렬 은 전형 적 인 분배 류 정렬 이 고 분배 류 정렬 은 분배 와 수집 두 가지 기본 조작 을 이용 하여 정렬 하 는 것 을 말한다.기수 정렬 은 반복 적 인 분배 와 수집 작업 을 통 해 정렬 을 완성 하고 기수 정렬 은 두 가지 정렬 방법 이 있 는데 그것 이 바로 '낮은 우선' 과 '높 은 우선' 이다.여기 서 나 는 '낮은 순위 우선' 정렬 법 으로 분석 했다.
1. 알고리즘 사상:
       정렬 할 때 먼저 가장 낮은 값 으로 기록 을 초보 적 으로 정렬 하고 이 를 바탕 으로 낮은 값 으로 정렬 합 니 다.이 를 통 해 낮은 위치 에서 높 은 위치 까지 모든 것 이 앞의 것 을 바탕 으로 키워드 key 의 한 사람 에 따라 모든 기록 을 정렬 하여 가장 높 은 위치 까지 정렬 하면 기수 정렬 의 전 과정 을 완성 할 수 있다.
2. 절차:
1) 가장 높 은 자리 가 끝 날 때 까지 최대 수의 자릿수 를 찾 아야 한다.
2) 정렬 후의 배열 을 저장 할 공간 을 엽 니 다.행렬 의 빠 른 전환 사상 을 이용 하여 count 배열 로 정렬 된 비트 와 같은 숫자의 개 수 를 저장 하고 start 배열 로 매번 시작 하 는 위 치 를 기록 하 며 모든 요 소 를 신속하게 포 지 셔 닝 합 니 다.
3) 원 시퀀스 에 다시 쓴다.
4) 가장 높 은 위치 에 있 을 때 까지 상기 절 차 를 반복 한다.
구체 적 인 실현 은 다음 과 같다.

void RadixSort(int *arr, int size)
{
 assert(arr);
 int *count = new int[10];//      0~9  
 int *start = new int[10];
 int *tmp = new int[size];//          
 int MaxRadix = GetMaxRadix(arr, size);//      
 int radix = 1;
 for (int k = 1; k <= MaxRadix; ++k)
 {
  memset(count, 0, sizeof(int)* 10);//   count
  memset(start, 0, sizeof(int)* 10);
  for (int i = 0; i < size; ++i)//count              
  {
   count[(arr[i] / radix) % 10]++;
  }
  start[0] = 0;
  for (int i = 1; i < 10; ++i)//start        
  {
   start[i] = start[i - 1] + count[i - 1];
  }
  for (int i = 0; i < size; ++i)//    
  {
   int num = (arr[i] / radix) % 10;
   tmp[start[num]++] = arr[i];
  }
  memcpy(arr, tmp, sizeof(int)*size);//  
  radix *= 10;
 }
 delete[] tmp;//    tmp
}

● 안정성 분석
      안정성 이란 정렬 후 원 시퀀스 에서 같은 데이터 의 상대 적 인 위치 가 바 뀌 지 않 는 다 는 것 을 말한다.정렬, 거품 정렬, 병합 정렬, 계수 정렬 과 기수 정렬 을 삽입 하 는 것 이 안정 적 입 니 다.빠 른 정렬, 힐 정렬, 쌓 기 정렬 과 선택 정렬 은 불안정 합 니 다.
● 복잡 도 분석
 1. 공간 복잡 도: 빠 른 정렬, 병합 정렬, 계수 정렬 과 기수 정렬 은 모두 공간 을 열 어야 한다. 정렬 삽입, 힐 정렬, 정렬 선택, 정렬, 거품 정렬 이 필요 하지 않 고 공간 복잡 도 는 O (1) 이다.
 2. 시간 복잡 도:
1) 삽입 정렬, 힐 정렬, 선택 정렬, 거품 정렬 은 모두 O (n ^ 2) 로 효율 이 낮다.정렬 효율 이 가장 낮은 것 을 선택 하 십시오. 가장 좋 은 상황 에서 시간 복잡 도 는 O (n ^ 2) 입 니 다.거품 정렬 과 삽입 정렬 을 비교 하면 삽입 정렬 이 비교적 좋다 (eg: 02, 1, 3, 4, 5, 6, 789; 삽입 정렬 은 한 번 에 완성 되 고 거품 정렬 은 두 번 이 필요 하 다). 거품 정렬 의 대가 가 비교적 크 며 최적화 (힐 정렬) 를 한 후에 삽입 하면 정렬 시간 을 더욱 단축 시 킬 수 있다.
 2) 더미 정렬, 병합 정렬, 빠 른 정렬 은 모두 O (n * lg (n) 이다.
      보통 최 악의 상황 을 보지 만 빠 른 정렬 (더 많은 최적화 가 존재 함) 은 최 악의 상황 이 거의 존재 하지 않 고 시간 복잡 도 는 O (n * lg (n) 이다.
      쌓 기 정렬 은 배열 만 정렬 할 수 있다 는 단점 이 있 습 니 다. 기수 정렬 과 계수 정렬 은 모두 한계 가 있 습 니 다 (데이터 밀집). 정렬 의 공간 복잡 도 는 O (n) 이 고 빠 른 정렬 은 O (lg (n) 입 니 다. 종합 하면 빠 른 정렬 이 가장 좋 습 니 다.
[건어물]
      정렬 을 병합 하면 내부 정렬 과 외부 정렬 이 존재 합 니 다.외부 정렬 이란 메모리 이외 의 (디스크 에 있 는) 데 이 터 를 정렬 할 수 있 는 것 을 말 합 니 다. 빅 데이터 의 파일 은 메모리 에 직접 불 러 와 정렬 할 수 없습니다. 파일 을 작은 파일 로 나 누 어 작은 파일 을 메모리 에 불 러 와 정렬 한 다음 에 정렬 된 데 이 터 를 다시 작성 하고 두 개의 질서 있 는 데이터 파일 을 다시 정렬 할 수 있 습 니 다.빅 데이터 파일 을 잘 배열 할 수 있 습 니 다.상기 사상 에 따라 파일 압축 의 실현 을 할 수 있 고 관심 이 있 는 것 은 스스로 해 볼 수 있다.