algorithm
기수 정렬

기수 정렬 기본 정보

기수 정렬 은 하한 비교 기반 알고리즘입니다. 이것은 비 비교 정수 정렬 알고리즘으로, 중요한 위치와 값을 공유하는 개별 숫자로 키를 그룹화하여 정수 키로 데이터를 정렬합니다. 기수 정렬은 요소가 1에서 k까지의 범위에있을 때 O (n + k) 시간을 정렬하는 선형 시간 정렬 알고리즘입니다. Radix Sort의 아이디어는 최하위 자리부터 최상위 자리까지 자릿수별로 정렬하는 것입니다. 기수 정렬은 계산할 정렬을 서브 루틴으로 사용하여 정렬합니다. 기수 정렬은 버킷 정렬의 일반화입니다.

Bucket Sort의 의사 코드 :

1. [0..n-1] 요소의 배열을 만듭니다.
2. 버킷 호출 각 요소의 가장 중요한 자릿수를 키로 반복하여 정렬합니다.
3. 소트 된 배열을 돌려줍니다.

기수 정렬의 예 :

우주 보조 장치 : O(n)
시간 복잡성 : O(n)