What is bucket sort

Bucket sorting is a sorting algorithm. The working principle is to divide the array into a limited number of buckets; bucket sorting is also an induction result of pigeonhole sorting. When the values ​​in the array to be sorted are When distributed evenly, bucket sorting uses linear time, but bucket sorting is not comparison sorting, and it is not affected by the "O(n log n)" lower limit.

Bucket sorting

If it is known that the value range of N keywords is from 0 to between M-1, and M is much smaller than N, the bucket sorting algorithm creates a "bucket" for each value of the keyword, that is, M buckets are created. When scanning N keywords, each key Put the words into the corresponding buckets, and then collect them in the order of the buckets to be naturally ordered

Introduction:

Bucket sort (Bucket sort) or so-called box sorting is a sorting algorithm , the working principle is to divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use other sorting algorithms or continue to use bucket sorting recursively). Bucket sort is an inductive result of pigeonhole sort. Bucket sort uses linear time (Θ(n)) when the values ​​in the array to be sorted are evenly distributed. But bucket sorting is not a comparison sorting, and it is not affected by the O(n log n) lower limit.

Definition

Assumption: The input is a uniformly distributed real number in the interval [0, 1) generated by a random process. Divide the interval [0, 1) into n sub-intervals (buckets) of equal size, each bucket size is 1/n: [0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k 1)/n),…distribute n input elements to these buckets, sort the elements in the buckets, and then connect the bucket inputs 0 ≤A[1. .n] <1 Auxiliary array B[0..n-1] is a pointer array, pointing to the bucket (linked list).

The above is the detailed content of What is bucket sort. For more information, please follow other related articles on the PHP Chinese website!