Preface: The topic of Java data structures and algorithms will be updated from time to time. Readers are welcome to supervise it. This article starts with the simplest sorting algorithm - bucket sorting, and analyzes the implementation ideas, code implementation, performance characteristics and applicable scenarios of bucket sorting.
0. Other sorting algorithm indexes
//www.VeVB.COM/article/120879.htm
1. Bucket sorting idea
A simple example:
Sorting the English test scores of 6 people (1~10 points). If the score is [6, 5, 8, 8, 10, 9], the idea of sorting with buckets is to prepare 10 buckets, the numbers are 1~10 in sequence, and the scores are placed in the corresponding buckets, such as 6 points into the No. 6 bucket, and two 8 points into the No. 8 bucket... and then output them one by one according to the order of the bucket numbers (if there is, if there is, if there is no one, no output). This is the basic idea of bucket sorting.
In fact, this is just a simple version. Just imagine, if the span range of elements to be sorted is relatively large, such as 1~10,000, do you need 10,000 buckets? In fact, in this case, one element is not always placed in a bucket, but many times multiple elements are placed in a bucket. In fact, real bucket sorting and hash list have the same principle.
In actual sorting, the elements in each bucket are usually sorted using other sorting algorithms, so more often, bucket sorting is used in combination with other sorting algorithms.
2. Bucket sorting code
After analyzing the idea of bucket sorting, you must first know the range of elements to be sorted. Taking the above as an example, declare an array of length 10 as 10 buckets, and then put the results one by one into the bucket, the value of the bucket is +1, and finally output the array subscript in reverse order. The value of each position of the array is output several times, so that the basic bucket sort can be achieved.
public class BucketSort { private int[] buckets; private int[] array; public BucketSort(int range,int[] array){ this.buckets = new int[range]; this.array = array; } /*Sorting*/ public void sort(){ if(array!=null && array.length>1){ for(int i=0;i<array.length;i++){ buckets[array[i]]++; } } } /*Sorting output*/ public void sortOut(){ //Reverse output data for (int i=buckets.length-1; i>=0; i--){ for(int j=0;j<buckets[i];j++){ System.out.print(i+"/t"); } } }}Test code:
public class SortTest { public static void main(String[] args) { testBucketsSort(); } private static void testBucketsSort(){ int[] array = {5,7,3,5,4,8,6,4,1,2}; BucketSort bs = new BucketSort(10, array); bs.sort(); bs.sortOut();//Output print sort}}3. Bucket sorting performance characteristics
Bucket sorting actually only requires iterating through all the elements to be sorted and then putting them in the specified position in sequence. If the output sorting time is added, all buckets need to be traversed. Therefore, the time complexity of bucket sorting is O(n+m), n is the number of elements to be sorted, and m is the number of buckets, that is, the range of elements to be sorted. This algorithm is a very fast sorting algorithm, but the spatial complexity is relatively large.
When the size range of elements to be arranged is relatively large, but the number of elements to be arranged is relatively small, space waste is more serious. The distribution of elements to be arranged is uniform every month, and the higher the space utilization rate, this is actually rare.
Through the above performance analysis, we can obtain the characteristics of bucket sorting: fast and simple, but at the same time, the space utilization is low. When the data to be sorted is large, the space utilization rate is unbearable.
4. Bucket sorting applicable scenarios
According to the characteristics of bucket sorting, bucket sorting is generally applicable to some specific environments, such as the data range is relatively limited or there are some specific requirements, such as the need to quickly obtain certain values through hash mapping, and the number of each number needs to be counted. But all of this is based on confirming the scope of the data. If the scope span is too large, consider using other algorithms.