Detailed explanation of the method of bucket sorting of Java number completion algorithm

This article mainly introduces the implementation method of bucket sorting of java data structure and algorithm. It analyzes the concept, principle, implementation method and related operation skills of bucket sorting in detail based on specific examples. Friends in need can refer to the following

The example of this article describes the implementation method of bucket sorting of java data structure and algorithm. Share it with everyone for your reference, the details are as follows:

Basic idea:

Assume that the input is generated by a random process [0, M ) uniformly distributed real numbers on the interval. Divide the interval [0, M) into n sub-intervals (buckets) of equal size, allocate n input elements to these buckets, sort the elements in the buckets, and then connect the buckets in sequence to input 0 ≤ A[1.. n] ArrayB[0..n-1] is an array of pointers, pointing to the bucket (linked list). Distribute n records to each bucket. If more than one record is assigned to the same bucket, sorting within the bucket is required. Finally, list the records in each bucket in order and remember them in an ordered sequence.

[Bucket - Keyword] MappingFunction

bindex=f(key) Where, bindex is the bucket The subscript of array B (i.e. the bindex bucket), k is the key of the column to be sorted. The key to the efficiency of bucket sorting lies in this mapping function, which must do: If the keyword k1Obviously, The determination of the mapping function has a great relationship with the characteristics of the data itself. Let’s give an example below:

If the column to be sorted K= {49, 38, 35, 97, 76, 73, 27, 49}. These data are all between 1-100. Therefore, we customize 10 buckets and determine the mapping function f(k)=k/10. Then the first keyword 49 will be positioned in the 4th bucket (49/10=4). Stack all keywords into buckets in turn, and perform quick sorting in each non-empty bucket to get the following picture:

As long as the order of the above picture is Output the data in each B[i] to get an ordered sequence.

The core code of the algorithm is as follows:

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

Bucket sorting cost analysis

Bucket Sorting uses the mapping relationship of functions to reduce almost all comparison work. In fact, the calculation of the f(k) value of bucket sort is equivalent to dividing in quick sort, which has divided a large amount of data into basically ordered data blocks (buckets). Then you only need to do advanced comparison sorting on a small amount of data in the bucket.

The time complexity of bucket sorting N keywords is divided into two parts:

(1) LoopCalculate the bucket of each keyword Mapping function, this time complexity is O(N).
(2) Use the advanced comparison sorting algorithm to sort all the data in each bucket, and its time complexity is ∑ O(Ni*logNi). Where Ni is the data volume of the i-th bucket.

Obviously, part (2) is the determining factor in the performance of bucket sort. Minimizing the number of data in the bucket is the only way to improve efficiency (because the best average time complexity based on comparison sorting can only reach O(N*logN)). Therefore, we need to try our best to achieve the following two points:

(1) The mapping function f(k) can evenly distribute N data to M buckets, so that each bucket has [ N/M] amount of data.
(2) Increase the number of buckets as much as possible. In the extreme case, only one data can be obtained from each bucket, thus completely avoiding the "comparison" sorting operation of the data in the bucket. Of course, it is not easy to do this. When the amount of data is huge, the f(k) function will cause a huge number of bucket sets, resulting in serious waste of space. This is a trade-off between time cost and space cost.

For N data to be sorted and M buckets, the average bucket sorting time complexity of [N/M] data per bucket is:

O (N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

When N=M, that is, in the extreme case, there is only one data in each bucket. The best efficiency of bucket sort can reach O(N).

Summary: The average time complexity of bucket sorting is linear O(N+C), where C=N*(logN-logM). If relative to the same N, the larger the number of buckets M, the higher the efficiency, and the best time complexity reaches O(N). Of course, the space complexity of bucket sorting is O(N+M). If the input data is very large and the number of buckets is also very large, the space cost will undoubtedly be expensive. Additionally, bucket sorting is stable.

That is, the following three points:

1. Bucket sorting is stable
2. Bucket sorting is the fastest among common sorting, faster than quick sort Even faster...in most cases
3. Bucket sorting is very fast, but it also consumes a lot of space. It is basically the most space-consuming sorting algorithm

Supplement:In the search algorithm, the best time complexity of the comparison-based search algorithm is also O(logN). For example, binary search, balanced binary tree, red-black tree, etc. However, the Hash table has a search efficiency of O(C) linear level (the search efficiency reaches O(1) without conflicts). So: Is the idea of ​​Hash table similar to bucket sorting?

In fact, bucket sorting has special requirements for data conditions. If the array is large, hundreds of millions of buckets will be allocated. It's obviously impossible. Therefore, bucket sorting has its limitations and is suitable for situations where the set of element values ​​is not large.

【Related Recommendations】

1. Special Recommendation: "php Programmer Toolbox" V0.1 version download

2. Java free video tutorial

2. Comprehensive analysis of Java annotations

The above is the detailed content of Detailed explanation of the method of bucket sorting of Java number completion algorithm. For more information, please follow other related articles on the PHP Chinese website!