Bucket Sort allocates the data to be sorted to a limited number of buckets and sorts the data in each Bucket. Bucket Sort is a linear time sorting algorithm. Each Bucket represents a range that can hold one or more elements.

  • Step 1: Create buckets equal to the number of elements to be sorted
  • Step 2: Determine the interval span of each bucket, because the last bucket only stores the maximum value of the data to be sorted, soInterval span = (Max - Min)/(Number of buckets - 1)
  • Step 3: Iterate over the data to be sorted and put each data check into each bucket
  • Step 4: Sort the elements in each bucket;
  • Step 5: Iterate through all buckets and output all elements in order as the final sorted elements.

Complexity analysis

Time complexity: O(n)

Java code implementation

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; public class BucketSort { public static void sort(double[] data) { if (data == null || data.length == 0) { return; } double Max = data[0]; double Max = data[0]; double min = data[0]; for (int i = 0; i < data.length; i++) { if (data[i] > max) { max = data[i]; } else if (data[i] < min) { min = data[i]; } } double d = max - min; Int bucketNum = data.length; // Initialize buckets. The number of buckets is equal to the number of data to be sorted. ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(); for (int i = 0; i < bucketNum; i++) { bucketList.add(new LinkedList<>()); } for (int I = 0; i < data.length; i++) { int num = (int) ((data[i] - min) * (bucketNum - 1) / d); bucketList.get(num).add(data[i]); } // For (int I = 0; i < bucketList.size(); i++) { Collections.sort(bucketList.get(i)); } // print all elements int index = 0; for (LinkedList<Double> list : bucketList) { for (double element : list) { data[index++] = element; }} public static void main(String[] args) {double[] data = {1.32, 1.68, 0.37, 1.16, 8.56, 3.25, 4.44, 6.54, 1.68, 2.66, 3.88, 5.49}; sort(data); System.out.println(Arrays.toString(data)); }}Copy the code

The results

[0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56]
Copy the code

Description:

(1) Find the maximum value 8.56 and minimum value 0.37 in the data to be sorted, and the difference value is 8.19

(2) Determine the number of buckets: 12 (equal to the number of data to be sorted)

(3) determine the interval span of each barrel :(8.56-0.37)/(12-1) = 0.75, and the interval range of each barrel is

[0.37, 1.06)  [1.06, 1.81)  [1.81, 2.56)  [2.56, 3.31)  [3.31, 4.06)  [4.06, 4.81)  [4.81, 5.56)  [5.56, 6.31)  [6.31, 7.06)  [7.06, 7.81)  [7.81, 8.56)  [8.56, 8.56]
Copy the code

(4) Iterate through the data to be sorted and put it into the corresponding bucket. Take 1.32 as an example, (1.32-0.37) * (12-1) / 8.19 = 1.27… , round to 1, put it into the second bucket, and the rest of the bucket loading process is as follows:

[1.32] [] [] [] [] [] [] [] [] [] [] [] [] [1.32, 1.68] [] [] [] [] [] [] [] [] [] [] [0.37] [1.32, 1.68] [] [] [] [] [] [] [] [] [] [] [0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] [] [0.37] [1.32, 1.68, 1.16] [] [] [] [] [] [] [] [] [] [8.56] [0.37] [1.32, 1.68, 1.16] [] [3.25] [] [] [] [] [] [] [] [8.56] [0.37] [1.32, 3.25, 1.68, 1.16] [] [] [] [4.44] [] [] [] [] [] [8.56] [0.37] [1.32, 1.68, 3.25 1.16] [] [] [] [4.44] [] [] [6.54] [] [] [8.56] [0.37] [1.32, 1.68, 1.16, 3.25 1.68] [] [] [] [4.44] [] [] [6.54] [] [] [8.56] [0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 4.44 2.66] [] [] [] [] [6.54] [] [] [8.56] [0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56] [0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [] [] [6.54] [] [] [8.56] [0.37] [1.32, 1.68, 1.16, 1.68] [] [3.25, 2.66] [3.88] [4.44] [5.49] [] [6.54] [] [] [8.56]Copy the code

(5) Perform sorting within each bucket

[0.37]  [1.16, 1.32, 1.68, 1.68]  []  [2.66, 3.25]  [3.88]  [4.44]  [5.49]  []  [6.54]  []  []  [8.56]
Copy the code

(6) Traverse all buckets and output them in sequence

0.37, 1.16, 1.32, 1.68, 1.68, 2.66, 3.25, 3.88, 4.44, 5.49, 6.54, 8.56
Copy the code