1. Problem solving ideas

        Bucket sorting is one of the simplest sorting algorithms. Bucket sorting has many similarities and origins with counting sorting and cardinal sorting. The important thing of bucket sorting is its idea, not its specific implementation. For different elements to be sorted, the specific implementation of bucket sorting will be different.

        The working principle of bucket sorting is to put the elements to be sorted into the corresponding bucket. Each bucket is sorted separately (it can be quick sort, recursive sort, or continue to use bucket sort in a recursive way). Bucket sorting requires four steps:

1) Design the barrel according to the element characteristics;

2) Put the elements to be sorted into the corresponding bucket;

3) Sort the elements in each bucket;

4) Combine the elements in the bucket to get an ordered sequence.

        Since it is sorting, the final result is either from large to small or from small to large. Bucket sorting first arranges the positions of buckets, and then puts elements into each bucket at one time. There are many ways to determine the number of buckets. You can define the number of buckets and the rules for putting elements into buckets according to the characteristics of the elements to be sorted. Usually, the elements to be sorted are evenly placed in the bucket according to the division method of the elements to be sorted.

Example:

Enter num = {7,10,21,6,13,39,58,22,40,52,32,50,46,29}    

Output nums  = {6,7,10,13,21,22,29,32,39,40,46,50,52}

By observing the characteristics of the elements in the array, you can design the rule for putting the bucket number: element value / 10. In this way, each element can be put into the corresponding bucket by division. The values of all elements in the left bucket are smaller than those in the right bucket. The placement process is shown in the following figure:

  When just put into the bucket, the size of each bucket can be determined relatively. The left side is smaller than the right side, but the bucket is still disordered. Sort each bucket separately. The sorting algorithm for sorting elements in the bucket can be selected by yourself:

Then according to the order of the bucket and the sequence in the bucket, a final ordered sequence is obtained.  

2 coding implementation

Coding implementation I:

You can use the idea of counting and sorting. The bucket contains the number of elements. The bucket number is the value of the element. The codes are as follows:

public static void bucketSort(int[] nums){

        //Find the maximum and minimum values
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i=0;i<nums.length;i++){
            max = Math.max(max,nums[i]);
            min = Math.min(min,nums[i]);
        }
        int k = max - min+1;//Calculate the number of barrels
        int[] tmp = new int[k];//Define K buckets
        //Calculate the number of occurrences of elements and count them into the bucket
        for (int i=0;i<nums.length;i++){
            tmp[nums[i]-min]++;
        }

        //Put the array to be sorted in its own position
        int x = 0;
        for (int i=0;i<tmp.length;i++){
            while (tmp[i]-->0){
                nums[x++] = i+min;
            }
        }

    }

Coding implementation 2:

Use the elements in the linked list bucket, sort the elements in the linked list in turn, and then merge the linked list to finally get an ordered array.

public static void bucketSort1(int[] nums){
        //Find the maximum and minimum values
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i=0;i<nums.length;i++){
            max = Math.max(max,nums[i]);
            min = Math.min(min,nums[i]);
        }
        int k = (max-min)/nums.length+1;
        ArrayList<ArrayList> list = new ArrayList<ArrayList>(k);
        for (int i=0;i<k;i++){
            list.add(new ArrayList<Integer>());
        }

        for (int i=0;i<nums.length;i++){
            list.get((nums[i]-min)/nums.length).add(nums[i]);
        }

        for (int i=0;i<list.size();i++){
            Collections.sort(list.get(i));
        }

        System.out.println(list.toString());
    }

3 time complexity and space complexity

Time complexity

         Suppose there are n numbers to be sorted. Divide it into m buckets. If it is evenly distributed, there are n/m elements in each bucket on average. The algorithm time complexity of bucket sorting consists of two parts:

• Traversal handles each element, ordinary traversal at the O(n) level
• Total time complexity of reordering in each bucket

For the first part, we should understand that the last ordered value traverses O(n), while in the second part, we can make such an analysis:

• If the elements in the bucket are evenly distributed, assuming that the sorting algorithm used in each bucket is fast sorting, the time complexity in each bucket is (n/m) log(n/m). If there are m buckets, the time complexity is m * (n/m)log(n/m)=n (log n-log m)

Therefore, the time complexity of final bucket sorting is: O(n)+O(n*(log n- log m))=O(n+n*(log n -log m))   Where m is the number of barrels. We sometimes write it as O(n+c), where c=n*(log n -log m);

Here, if the limit case n=m is reached. It can ensure that sorting in the bucket is avoided. Putting the values in the bucket does not need to be sorted again to achieve the sorting effect of O(n). Of course, this situation belongs to counting sorting. Please explain the counting sorting in detail later and remember to review it again.

Spatial complexity

        Bucket sorting is a typical sorting algorithm that uses space for time. Is an extension of count sorting. Bucket sorting needs to define multiple buckets that can accommodate all the elements to be sorted. If sorting algorithms with spatial complexity of O(1) such as quick sorting are used in the bucket, the spatial complexity of bucket sorting depends on the capacity synthesis of the bucket, S(n) = O(n+1). If other sorting algorithms requiring additional space are used in the bucket, the spatial complexity of bucket sorting is the synthesis of the two spatial complexity, S (n) = O(n+k)