Shulou(Shulou.com)06/03 Report--

What is bucket sorting? In view of this problem, this article introduces the corresponding analysis and answers in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible way.

Bucket sorting is a sorting algorithm, which works by dividing the array into a limited number of buckets; bucket sorting is also an inductive result of pigeon nest sorting, when the values in the array to be sorted are evenly distributed, bucket sorting uses linear time, but bucket sorting is not a comparative sort, it is not affected by the lower bound of "O (n log n)".

Bucket sort

If it is known that the value range of N keywords is between 0 and Mmur1, and M is much smaller than N, the bucket sorting algorithm establishes a "bucket" for each keyword, that is, M buckets. When scanning N keywords, put each keyword into the corresponding bucket, and then collect it in the order of the bucket.

Brief introduction:

Bucket sort, or so-called box sorting, is a sorting algorithm that works by dividing an array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue to sort recursively using bucket sorting). Bucket sorting is an inductive result of pigeon nest sorting. Bucket sorting uses linear time (theta (n)) when the values in the array to be sorted are evenly distributed. But bucket sorting is not a comparative sort, and it is not affected by the lower bound of O (n log n).

Define

It is assumed that the input is a real number uniformly distributed on the interval [0,1) generated by a random process. The interval [0,1) is divided into n equal-sized sub-zones (buckets). Each barrel is sized as follows: [0,1], [1, 2), [2, 3), … , [KBO, (Kraft 1) / n), … Assign n input elements to these buckets, sort the elements in the bucket, and then join the bucket by entering 0 ≤ A [1.. n].

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.