서문 : Java 데이터 구조 및 알고리즘의 주제는 때때로 업데이트됩니다. 독자들은 그것을 감독 할 수 있습니다. 이 기사는 가장 간단한 정렬 알고리즘 - 버킷 분류로 시작하여 구현 아이디어, 코드 구현, 성능 특성 및 버킷 분류의 적용 가능한 시나리오를 분석합니다.
0. 기타 정렬 알고리즘 인덱스
//www.vevb.com/article/120879.htm
1. 버킷 분류 아이디어
간단한 예 :
영어 시험 점수를 6 명 (1 ~ 10 포인트) 정렬합니다. 점수가 [6, 5, 8, 8, 10, 9] 인 경우, 버킷과 정렬하는 아이디어는 10 개의 버킷을 준비하고, 숫자는 순서대로 1 ~ 10이며, 점수는 6 번 버킷에 6 점, 8 번 버킷에 대한 2 개의 8 점을 출력합니다. 이것은 버킷 분류의 기본 아이디어입니다.
사실, 이것은 단순한 버전 일뿐입니다. 분류 할 요소의 스팬 범위가 1 ~ 10,000과 같이 비교적 크다면 10,000 버킷이 필요합니까? 실제로이 경우 하나의 요소가 항상 버킷에 배치되는 것은 아니지만 여러 번 여러 요소가 양동이에 배치됩니다. 실제로 실제 버킷 분류 및 해시 목록은 동일한 원칙을 가지고 있습니다.
실제 정렬에서 각 버킷의 요소는 일반적으로 다른 분류 알고리즘을 사용하여 정렬되므로 버킷 분류는 다른 분류 알고리즘과 함께 사용됩니다.
2. 버킷 분류 코드
버킷 분류의 아이디어를 분석 한 후 먼저 정렬 할 요소 범위를 알아야합니다. 위의 예를 들어, 길이 10의 배열을 10 개의 버킷으로 선언 한 다음 결과를 하나씩 버킷에 넣고 버킷의 값은 +1이며 마지막으로 배열 첨자를 역 순서로 출력하십시오. 배열의 각 위치의 값은 여러 번 출력되므로 기본 버킷 정렬을 달성 할 수 있습니다.
공개 클래스 BucketSort {private int [] 버킷; 개인 int [] 배열; public bucketsort (int range, int [] array) {this.buckets = new int [범위]; this.array = 배열; } /*정렬* / public void sort () {if (array! = null && array.length> 1) {for (int i = 0; i <array.length; i ++) {버킷 [배열 [i]] ++; }}}/*출력 정렬*/public void sortout () {// (int i = bucts.length-1; i> = 0; i-) {for (int j = 0; j <버킷 [i]; j ++) {system.out.print (i+"/t"); }}}}테스트 코드 :
공개 클래스 SortTest {public static void main (String [] args) {testBucketSsort (); } private static void testbucketssort () {int [] array = {5,7,3,5,4,8,4,4,1,2}; BucketSort BS = New BucketSort (10, 배열); bs.sort (); bs.sortout (); // 출력 인쇄 정렬}}3. 버킷 분류 성능 특성
버킷 분류는 실제로 모든 요소를 통한 반복을 정렬 한 다음 지정된 위치에 순서대로 배치하면됩니다. 출력 분류 시간이 추가되면 모든 버킷을 통과해야합니다. 따라서, 버킷 분류의 시간 복잡성은 O (n+m)이고, n은 정렬 할 요소의 수이고, m은 버킷의 수, 즉 정렬 할 요소의 범위입니다. 이 알고리즘은 매우 빠른 분류 알고리즘이지만 공간 복잡성은 비교적 큽니다.
배열 될 요소의 크기 범위가 비교적 크지 만 배열 될 요소의 수는 비교적 작으며 공간 폐기물이 더 심각합니다. 배열 될 요소의 분포는 매달 균일하며 공간 활용률이 높을수록 실제로는 드 rare니다.
위의 성능 분석을 통해 버킷 분류의 특성을 얻을 수 있지만 빠르고 단순하지만 동시에 공간 활용이 낮습니다. 정렬 할 데이터가 클 경우 공간 활용률은 견딜 수 없습니다.
4. 버킷 분류 해당 시나리오
버킷 분류의 특성에 따르면, 버킷 분류는 일반적으로 데이터 범위가 비교적 제한적이거나 해시 매핑을 통해 특정 값을 신속하게 얻어야 할 필요성과 같은 특정 요구 사항이있는 것과 같은 일부 특정 환경에 일반적으로 적용됩니다. 각 숫자의 수를 계산해야합니다. 그러나이 모든 것은 데이터의 범위를 확인하는 데 기반을두고 있습니다. 범위 범위가 너무 크면 다른 알고리즘을 사용하는 것을 고려하십시오.