정렬. - 통 정렬.

통 정렬 (Bucket Sort) 통 정렬 은 계수 정렬 의 업그레이드 버 전 입 니 다.그것 은 함수 의 매 핑 관 계 를 이용 하 였 으 며, 효율 여부 의 관건 은 바로 이 매 핑 함수 의 확정 에 있다.통 정렬 (Bucket sort) 의 작업 원리: 입력 데이터 가 균일 한 분포 에 따른다 고 가정 하고 데 이 터 를 제 한 된 수량의 통 에 나 누 어 각각 정렬 합 니 다 (다른 정렬 알고리즘 을 사용 하거나 재 귀 방식 으로 통 정렬 을 계속 할 수 있 습 니 다.
알고리즘 설명 자 는 사람 이 하나의 BucketSize 를 설정 하고 통 마다 몇 개의 서로 다른 수 치 를 배치 할 수 있 는 지 설명 합 니 다 (예 를 들 어 BucketSize = = 5 시 에 이 통 은 (1, 2, 3, 4, 5 곶 이라는 몇 가지 숫자 를 저장 할 수 있 지만 용량 에 제한 이 없 으 면 100 개 3 을 저장 할 수 있 습 니 다).; 입력 한 데 이 터 를 옮 겨 다 니 며 데 이 터 를 하나씩 해당 하 는 통 에 넣 고, 빈 통 이 아 닌 통 마다 정렬 할 수 있 으 며, 다른 정렬 방법 을 사용 할 수도 있 고, 재 귀적 으로 통 으로 정렬 할 수도 있 습 니 다. 빈 통 이 아 닌 통 에서 정렬 된 데 이 터 를 연결 할 수도 있 습 니 다. 재 귀적 으로 통 을 각 통 으로 정렬 할 경우, 통 수가 1 일 때 수 동 으로 BucketSize 를 줄 여야 합 니 다.다음 순환 통 의 수 를 증가 시 킵 니 다. 그렇지 않 으 면 순환 에 빠 져 메모리 가 넘 칩 니 다.
알고리즘 분석 통 정렬 이 가장 좋 은 상황 에서 선형 시간 O (n) 를 사용 하고 통 정렬 의 시간 복잡 도 는 각 통 간 의 데 이 터 를 정렬 하 는 시간 복잡 도 에 달 려 있다. 다른 부분의 시간 복잡 도 는 모두 O (n) 이기 때문이다.. 분명 한 것 은 통 의 구분 이 작 을 수록 각 통 간 의 데이터 가 적 고 정렬 에 걸 리 는 시간 도 적 을 것 입 니 다. 그러나 해당 하 는 공간 소 모 는 커 집 니 다. 최 적 상황: T (n) = O (n + k) 최 악의 상황: T (n) = O (n + k) 평균 상황: T (n) = O (n2)
자바 알고리즘 구현:

public static void bucketSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		int[] bucket = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]]++;
		}
		int i = 0;
		for (int j = 0; j < bucket.length; j++) {
			while (bucket[j]-- > 0) {
				arr[i++] = j;
			}
		}
	}

사진 설명 박문:https://blog.csdn.net/hellozhxy/article/details/79911867