leetcode-java/src/sort/BucketSort.java at master · fluency03/leetcode-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * BucketSort: mainly sort an array with elements uniformly distributed over a range.
 *
 * Worst Case Time Complexity: O(n^2).
 * Best and Average Case Time Complexity: O(n + k).
 * Space Complexity: O(n * k).
 *
 */

importjava.util.Arrays;
importjava.util.List;
importjava.util.ArrayList;

/**
 * http://www.growingwiththeweb.com/2015/06/bucket-sort.html
 */
publicclassBucketSort {

privatestaticfinalintDEFAULT_BUCKET_SIZE = 5;

publicstaticvoidsort(int[] arr) {
bucketSort(arr, DEFAULT_BUCKET_SIZE);
 }

publicstaticvoidbucketSort(intarr[], intsize) {
if (arr.length == 0) return;

IntegerminValue = arr[0];
IntegermaxValue = arr[0];
for (inti = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
 } elseif (arr[i] > maxValue) {
maxValue = arr[i];
 }
 }

intbucketCount = (maxValue - minValue) / size + 1;
List<List<Integer>> buckets = newArrayList<List<Integer>>(bucketCount);
for (inti = 0; i < bucketCount; i++) {
buckets.add(newArrayList<Integer>());
 }

for (inti = 0; i < arr.length; i++) {
buckets.get((arr[i] - minValue) / size).add(arr[i]);
 }

intcurrentIndex = 0;
for (inti = 0; i < buckets.size(); i++) {
Integer[] bucketArray = newInteger[buckets.get(i).size()];
bucketArray = buckets.get(i).toArray(bucketArray);
InsertionSort.sort(bucketArray);
for (intj = 0; j < bucketArray.length; j++) {
arr[currentIndex++] = bucketArray[j];
 }
 }
 }

publicstaticvoidmain(String[] args) {
int[] arr1 = {10, 3, 7, 5, 1, 15, 20};
BucketSort.sort(arr1);
System.out.println(Arrays.toString(arr1));

int[] arr2 = {};
BucketSort.sort(arr2);
System.out.println(Arrays.toString(arr2));

int[] arr3 = {10};
BucketSort.sort(arr3);
System.out.println(Arrays.toString(arr3));
 }

}