수색…
버킷 정렬 기본 정보
버킷 정렬 은 입력 배열의 요소가 버킷으로 분산되는 정렬 알고리즘입니다. 모든 요소를 배포 한 후 버킷은 다른 정렬 알고리즘으로 개별적으로 정렬됩니다. 때로는 재귀 적 방법으로 정렬되기도합니다.
Bucket Sort의 의사 코드
- n을 입력리스트 L의 길이 라하자.
- L로부터의 각 요소 i에 대해
- B [i]가 비어 있지 않으면
- A [i]를 B [i]에 넣는다;
- 그렇지 않으면 B [i] : = A [i]
- Concat B [i .. n]를 하나의 정렬 된 목록으로 반환합니다.
대부분 사람들은 약간의 최적화를 위해 삽입 패러다임을 사용합니다.
보조 공간 : O{n}
C # 구현
public class BucketSort
{
public static void SortBucket(ref int[] input)
{
int minValue = input[0];
int maxValue = input[0];
int k = 0;
for (int i = input.Length - 1; i >= 1; i--)
{
if (input[i] > maxValue) maxValue = input[i];
if (input[i] < minValue) minValue = input[i];
}
List<int>[] bucket = new List<int>[maxValue - minValue + 1];
for (int i = bucket.Length - 1; i >= 0; i--)
{
bucket[i] = new List<int>();
}
foreach (int i in input)
{
bucket[i - minValue].Add(i);
}
foreach (List<int> b in bucket)
{
if (b.Count > 0)
{
foreach (int t in b)
{
input[k] = t;
k++;
}
}
}
}
public static int[] Main(int[] input)
{
SortBucket(ref input);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow