재 학 데이터 구조 002 - 통 정렬, 기수 정렬

1. 통 정렬
 
        N 개의 정수 가 있 고 범 위 는 1 - M 또는 0 - M - 1 이다.배열 Count 를 남 겨 두 고 크기 는 M 이 며 0 으로 초기 화 합 니 다.그래서 Count 는 M 개의 단원 (또는 통) 이 있 습 니 다.Ai 가 읽 혔 을 때 Count [Ai] 가 1 증가 합 니 다.모든 입력 이 읽 히 면 Count 를 스 캔 하고 출력 정렬 번호 의 목록 을 출력 합 니 다.통 정렬 구현 코드 는 다음 과 같 습 니 다.
 

  
  
  
  

   
   
   
   
#include <stdio.h> 
   
   
   
   
#define Max 10 
   
   
   
   
 
   
   
   
   
void initArray(int arr[], int len) 
   
   
   
   
{ 
   
   
   
   
    int k; 
   
   
   
   
    for(k = 0; k < len; k++) 
   
   
   
   
    { 
   
   
   
   
        arr[k] = 0; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void PrintBucketArray(int BucketArr[], int len) 
   
   
   
   
{ 
   
   
   
   
    int j; 
   
   
   
   
    for(j = 0; j < len; j++) 
   
   
   
   
    { 
   
   
   
   
        int tmp = BucketArr[j]; 
   
   
   
   
        while((tmp--) > 0) 
   
   
   
   
        { 
   
   
   
   
            printf("%d
",j); 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
/************************************************ 
   
   
   
   
*   ，           0-Max-1   
   
   
   
   
* 
   
   
   
   
************************************************/ 
   
   
   
   
void BucketSort(int input[], int la, int output[], int lb) 
   
   
   
   
{ 
   
   
   
   
    initArray(output,lb); 
   
   
   
   
    int i; 
   
   
   
   
    for(i = 0; i < la; i++) 
   
   
   
   
    { 
   
   
   
   
        output[input[i]]++; 
   
   
   
   
    } 
   
   
   
   
    PrintBucketArray(output,lb); 
   
   
   
   
} 
   
   
   
   
int main(void) 
   
   
   
   
{ 
   
   
   
   
    int a[10] = {9,8,8,5,1,3,3,3,2,2}; 
   
   
   
   
    int b[Max]; 
   
   
   
   
    BucketSort(a,10,b,Max); 
   
   
   
   
    return 0; 
   
   
   
   
} 
  
  
  
  

 
2. 기수 정렬
    기수 정렬 은 통 정렬 의 홍보 입 니 다. N 개 수 는 0 - NP - 1 사이 에 있 습 니 다 (P 는 상수 입 니 다).이런 상황 에 서 는 통 으로 정렬 하 는 것 이 적합 하지 않다.한 번 에 해결 할 수 없 으 니 절차 에 따라 여러 번 처리 하 는 것 을 고려 할 수 있다.기수 정렬 의 사고: 정렬 된 수의 가장 낮은 유효 위 치 를 통 으로 정렬 합 니 다.즉, 각 수 를 최저 위치 로 통 순 서 를 매 긴 다음 에 낮은 통 순 서 를 매 긴 다 는 것 이다.    예 를 들 면 가장 좋 은 설명 이다.현재 10 개 수: 64, 8, 216, 512, 27, 729, 0, 1, 343, 125.10 개의 수 는 모두 0 - 999 (10 ^ 3 - 1) 사이 에 떨어진다.    먼저 최저 위치 에 따라 정렬 한 결 과 는 다음 과 같다.
0
1
512
343
64
125
216
27
8
729
0
1
2
3
4
5
6
7
8
9
    그리고 순서대로 정렬 한 결과 다음 과 같은 결 과 를 얻 었 습 니 다.
08 01 00
216 512
729 27 125
 
343
 
64
 
 
 
0
1
2
3
4
5
6
7
8
9
    이 어 꼴찌 세 번 째 로 정렬 한 결과:
 
064 027 008 001 000
125
216
343
 
512
 
729
 
 
0
1
2
3
4
5
6
7
8
9
    기수 정렬 코드 를 다시 보충 합 니 다.