[정렬 알고리즘] - 통 정렬 자바 구현

오늘 leetcode 를 칠 할 때 41 문제 First Missing Positive 에서 정렬 알고리즘 에 통 정렬 이 하나 더 있 는 것 을 발견 하고 정리 도 했다.
통 정렬
통 정렬 에 대해 먼저 몇 가지 설명 을 하 세 요.
1) 통 정렬 은 안정 적 이다.2) 통 정렬 은 흔히 볼 수 있 는 정렬 알고리즘 중 가장 빠 른 것 이다. 대부분 상황 에서 빠 른 배열 과 병합 정렬 보다 빠르다. 3) 통 정렬 은 매우 빠 르 지만 공간 도 매우 소모 된다. 전형 적 인 공간 으로 시간 을 바 꾸 고 대체적으로 메모리 가 가장 소모 되 는 정렬 알고리즘 이다.
통 정렬 중: 무질서 한 배열 은 구성원 이 고정 (유한 한) 구간 에 속 하 는 것 을 요구 합 니 다. 예 를 들 어 범 위 는 0 - 9 입 니 다.
예 를 들 어 대기 숫자 [6, 2, 4, 1, 5, 9]
빈 통 10 개, 최대 빈 통 몇 개 준비

[6 2 4 1 5 9]               

[0 0 0 0 0 0 0 0 0 0]     

[0 1 2 3 4 5 6 7 8 9]      (     )

1) 순서 대기 배열 에서 숫자 를 꺼 내 고 먼저 6 을 꺼 낸 다음 6 을 6 번 통 에 넣는다. 이 과정 은 이와 유사 하 다. 빈 통 [대기 배열 [0] = 대기 배열 [0]
[6, 2, 4, 1, 5, 9] 대기 배열.
[0 0 0 0 0 6 0 0] 빈 통
[0 1 2 3 4 5 6 7 8 9] 통 번호 (실제 존재 하지 않 음)
2) 배열 대기 배열 에서 다음 숫자 를 꺼 내 는 순서
[6, 2, 4, 1, 5, 9] 대기 배열.
[0, 02, 0, 0, 6, 0] 빈 통
[0 1 2 3 4 5 6 7 8 9] 통 번호 (실제 존재 하지 않 음)
3, 4, 5, 6 생략, 과정 과 마찬가지 로 모두 통 에 들 어가 면 아래 가 이렇게 됩 니 다.
[6, 2, 4, 1, 5, 9] 대기 배열.
[0 1, 2, 0, 4, 5, 6, 0, 9] 빈 통.
[0 1 2 3 4 5 6 7 8 9] 통 번호 (실제 존재 하지 않 음)
0 은 빈 통, 건 너 뛰 기, 순서대로 꺼 내 면 됩 니 다. 1, 2, 4, 5, 6, 9.
예제 원본 코드:

public static int[] bucketSort(int[] nums, int maxNum){
    int[] sorted = new int[maxNum+1];

    for(int i=0; i//            
    }
    return sorted;
}

테스트 코드:

public static void main(String[] args) {
    int[] x = { 99, 65, 24, 47, 50, 88,33, 66, 67, 31, 18 };
    int[] sorted = bucketSort(x, 99);
    for (int i = 0; i < sorted.length; i++)
    {
        if (sorted[i] > 0)
            System.out.println(sorted[i]);
    }
}

출력:

18, 24, 31, 33, 47, 50, 65, 66, 67, 88, 99, 

본문 전체 코드 의 github 주소:https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/BucketSort.java