데이터 구조 002 - 통 정렬, 기수 정렬
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
기수 정렬 코드 를 다시 보충 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
