Java 숫자 완성 알고리즘의 버킷 정렬 방법에 대한 자세한 설명

이 글에서는 주로 Java 데이터 구조와 알고리즘에서 버킷 정렬의 구현 방법을 소개합니다. 구체적인 예를 바탕으로 버킷 정렬의 개념, 원리, 구현 방법 및 관련 작동 기술을 자세히 분석합니다.

본 글의 예시에서는 자바 데이터 구조와 알고리즘의 버킷 정렬 구현 방법을 설명한다. 다음과 같이 참고할 수 있도록 모든 사람과 공유하세요.

기본 아이디어:

입력이 무작위 프로세스에 의해 생성된다고 가정합니다. [0 , M ) 구간에 균일하게 분포된 실수입니다. 구간 [0, M)을 동일한 크기의 n개의 하위 구간(버킷)으로 나누고, 이 버킷에 n개의 입력 요소를 할당하고, 버킷의 요소를 정렬한 다음, 버킷을 순서대로 연결하여 0 ≤ A[1을 입력합니다. .n] ArrayB[0..n-1]은 버킷(연결된 목록)을 가리키는 포인터 배열입니다. 각 버킷에 n개의 레코드를 배포합니다. 동일한 버킷에 두 개 이상의 레코드가 할당된 경우 버킷 내에서 정렬이 필요합니다. 마지막으로 각 버킷의 레코드를 순서대로 나열하고 순서대로 기억합니다.

[Bucket - 키워드] MappingFunction

bindex=f(key) 여기서 BINDEX는 버킷입니다. 배열 B(즉, BINDEX 버킷)의 첨자, k는 정렬할 열의 키입니다. 버킷 정렬 효율성의 핵심은 다음을 수행해야 하는 매핑 함수에 있습니다. 키워드 k1물론 매핑 함수의 결정은 데이터 자체의 특성과 큰 관계가 있습니다. 아래 예를 들어보겠습니다.

정렬할 열이 K= { 49, 38, 35, 97, 76, 73, 27, 49}. 이 데이터는 모두 1-100 사이입니다. 따라서 우리는 10개의 버킷을 맞춤화하고 매핑 함수 f(k)=k/10을 결정합니다. 그러면 첫 번째 키워드 49가 네 번째 버킷(49/10=4)에 배치됩니다. 모든 키워드를 차례로 버킷에 쌓고 비어 있지 않은 각 버킷에서 빠른 정렬을 수행하여 다음 그림을 얻습니다.

위 그림의 순서가 출력인 경우 각 B[i]의 데이터를 정렬하여 순서가 지정된 시퀀스를 얻습니다.

알고리즘의 핵심 코드는 다음과 같습니다.

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

버킷 정렬 비용 분석

Bucket Sorting은 함수의 매핑 관계를 사용하여 거의 모든 비교 작업을 줄입니다. 실제로 버킷 정렬의 f(k) 값 계산은 대량의 데이터를 기본적으로 정렬된 데이터 블록(버킷)으로 나누는 퀵 정렬의 분할과 동일합니다. 그런 다음 버킷에 있는 소량의 데이터에 대해서만 고급 비교 정렬을 수행하면 됩니다.

N개의 키워드를 버킷 정렬하는 시간복잡도는 두 부분으로 나뉜다.

(1) 루프각 키워드의 버킷을 계산하는 매핑 함수, 이번에는 복잡도는 O(N)입니다.
(2) 고급 비교 정렬 알고리즘을 사용하여 각 버킷의 모든 데이터를 정렬하며 시간 복잡도는 ∑ O(Ni*logNi)입니다. 여기서 Ni는 i번째 버킷의 데이터 볼륨입니다.

물론 (2)번 부분이 버킷 정렬의 성능을 좌우하는 요소이다. 버킷에 있는 데이터 수를 최소화하는 것이 효율성을 높이는 유일한 방법입니다(비교 정렬을 기반으로 한 최고의 평균 시간 복잡도는 O(N*logN)에만 도달할 수 있기 때문입니다). 따라서 우리는 다음 두 가지 점을 달성하기 위해 최선을 다해야 합니다.

(1) 매핑 함수 f(k)는 N개의 데이터를 M개의 버킷에 균등하게 배포할 수 있으므로 각 버킷에는 [N /M] 데이터 양.
(2) 버킷 수를 최대한 늘립니다. 극단적인 경우에는 각 버킷에서 하나의 데이터만 얻을 수 있으므로 버킷에 있는 데이터의 "비교" 정렬 작업을 완전히 피할 수 있습니다. 물론 데이터 양이 많을 경우 f(k) 함수를 사용하면 엄청난 수의 버킷 세트가 발생하여 심각한 공간 낭비가 발생합니다. 이는 시간 비용과 공간 비용 간의 균형입니다.

정렬할 데이터 N개와 버킷 M개에 대해 버킷당 [N/M]개 데이터의 평균 버킷 정렬 시간 복잡도는

O(N)+입니다. O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

N=M인 경우, 즉 극단적인 경우 각 버킷에는 데이터가 하나만 있습니다. 버킷 정렬의 최고 효율은 O(N)에 도달할 수 있습니다.

요약: 버킷 정렬의 평균 시간 복잡도는 선형 O(N+C)입니다. 여기서 C=N*(logN-logM)입니다. 동일한 N에 대해 버킷 M의 수가 많을수록 효율성이 높아지며, 최적의 시간 복잡도는 O(N)에 이릅니다. 물론, 버킷 정렬의 공간 복잡도는 O(N+M)이다. 입력 데이터가 매우 크고 버킷의 개수도 매우 많으면 공간 비용이 당연히 비싸게 된다. 또한 버킷 정렬이 안정적입니다.

즉, 다음 세 가지 사항입니다.

1. 버킷 정렬이 안정적입니다
2. 버킷 정렬은 일반 정렬 중 가장 빠르며, 퀵 정렬보다 좋습니다. 더 빠릅니다...대부분의 경우
3. 버킷 정렬은 매우 빠르지만 공간을 많이 소모합니다

보충: 검색 알고리즘에서 비교 기반 검색 알고리즘의 최고 시간 복잡도도 O(logN)입니다. 예를 들어 이진 검색, 균형 이진 트리, 레드-블랙 트리 등이 있습니다. 그러나 Hash 테이블의 검색 효율성은 O(C) 선형 수준입니다(검색 효율성은 충돌 없이 O(1)에 도달함). 그렇다면 해시 테이블의 개념은 버킷 정렬과 비슷합니까?

사실 버킷 정렬에는 데이터 조건에 대한 특별한 요구 사항이 있습니다. 배열이 크면 수억 개의 버킷이 할당됩니다. 불가능한. 따라서 버킷 정렬에는 한계가 있으며 요소 값의 집합이 크지 않은 상황에 적합합니다.

【관련 추천사항】

1. 특별 추천: "php Programmer Toolbox" V0.1 버전 다운로드

2. 무료 Java 동영상 튜토리얼

2. Java 주석 종합 분석

위 내용은 Java 숫자 완성 알고리즘의 버킷 정렬 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!