데이터 구조 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
        그리고 순서대로 정렬 한 결과 다음 과 같은 결 과 를 얻 었 습 니 다.
080100
216 512
729 27 125
343
64
0
1
2
3
4
5
6
7
8
9
        이 어 꼴찌 세 번 째 로 정렬 한 결과:
064027008001000
125
216
343
512
729
0
1
2
3
4
5
6
7
8
9
        기수 정렬 코드 를 다시 보충 합 니 다.

좋은 웹페이지 즐겨찾기