Summary of knowledge points about bucket sorting in Java

Foreword: the Symposium on Java data structure and algorithm is updated from time to time. Readers are welcome to supervise. This paper starts with the simplest sorting algorithm bucket sorting, and analyzes the implementation idea, code implementation, performance characteristics and applicable scenarios of bucket sorting.

0. Index of other sorting algorithms

https://www.oudahe.com/p/40898/

1. Bucket sorting idea

A simple example:

Sort the English test scores (1 ~ 10 points) of 6 people. If the scores are [6,5,8,10,9], the idea of sorting with buckets is to prepare 10 buckets with numbers of 1 ~ 10, put the scores into the corresponding buckets, for example, 6 points into bucket 6, and two 8 points into bucket 8... And then output them one by one according to the bucket label order This is the basic idea of bucket sorting.

In fact, this is just a simple version. Imagine that if the span of the elements to be sorted is large, such as 1 ~ 10000, does it need 10000 barrels? In fact, in this case, one element is not always put in a bucket, and many times, multiple elements are put in a bucket. In fact, the real bucket sorting and hash table have the same principle.

In actual sorting, other sorting algorithms are usually used to sort the elements in each bucket, so bucket sorting will be used together with other sorting algorithms more often.

2. Bucket sort code

After analyzing the idea of bucket sorting, we should first know the range of elements to be sorted. Taking the above as an example, declare an array with a length of 10 as 10 buckets, and then put the scores into the bucket one by one, the value of the bucket is + 1. Finally, the array subscript is output in reverse order, and the value of each position of the array is output several times, so as to realize the basic bucket sorting.

Test code:

3. Performance characteristics of bucket sorting

Bucket sorting actually only needs to traverse all the elements to be arranged, and then put them in the specified position in turn. If you add the output sorting time, you have to traverse all buckets. Therefore, the time complexity of bucket sorting is O (n + m), n is the number of elements to be arranged, and M is the number of buckets, that is, the range of elements to be arranged. This algorithm is a very fast sorting algorithm, but the space 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, the space waste is more serious. The elements to be arranged are evenly distributed every month, and the higher the space utilization is. In fact, this situation is very rare.

Through the above performance analysis, we can get the characteristics of bucket sorting: fast and simple, but at the same time, the space utilization is low. When the waiting data span is large, the space utilization is unbearable.

4. Bucket sorting applicable scenario

According to the characteristics of bucket sorting, bucket sorting is generally applicable to some specific environments. For example, the data range is limited or there are some specific requirements. For example, it is necessary to quickly obtain some values through hash mapping and count the number of each number. However, all this is based on the premise of confirming the range of data. If the range span is too large, other algorithms will be considered.