수색…
기본 정보 정렬 계산
계수 소트 는 객체의 키에 따라 정렬되는 객체 모음에 대한 정수 정렬 알고리즘입니다.
단계
- 입력 배열 A 의 범위와 동일한 크기를 갖는 작업 배열 C를 생성 합니다.
- C는 [X] 시간 (X)의 개수에 기초한 출연 할당하는 반복.
- C 를 배열로 변환합니다. 여기서 C [x]는 배열을 반복하여 각 C [x]에 이전 값과 그 앞에 오는 C의 모든 값의 합을 할당하여 ≤ x의 수를 나타냅니다.
- A를 거꾸로 반복하면서 각 값을 C에 기록 된 인덱스의 새로운 정렬 된 배열 B 에 배치합니다. 이것은 대해 수행되는 소정의 A [X]에 할당 B가 [C [A는 [X]] A [X] 및 감분 C에 [A는 [X]의 경우에 원래 정렬되지 않은 배열 중복 값이 있었다.
소계 계산의 예
보조 공간 : O(n+k)
시간 복잡성 : 최악의 경우 : O(n+k)
, 최상의 경우 : O(n)
, 평균의 경우 O(n+k)
Psuedocode 구현
제약 조건 :
- 입력 (소트 할 배열)
- 입력 요소 수 (n)
- 0..k-1 (k)의 범위에있는 키
- 수 (수의 배열)
의사 코드 :
for x in input:
count[key(x)] += 1
total = 0
for i in range(k):
oldCount = count[i]
count[i] = total
total += oldCount
for x in input:
output[count[key(x)]] = x
count[key(x)] += 1
return output
C # 구현
public class CountingSort
{
public static void SortCounting(int[] input, int min, int max)
{
var count = new int[max - min + 1];
var z = 0;
for (var i = 0; i < count.Length; i++)
count[i] = 0;
foreach (int i in input)
count[i - min]++;
for (var i = min; i <= max; i++)
{
while (count[i - min]-- > 0)
{
input[z] = i;
++z;
}
}
}
public static int[] Main(int[] input)
{
SortCounting(input, input.Min(), input.Max());
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow