Bucket sort is an upgraded version of counting sort, which makes up for the limitation of counting sort

What is bucket sort

A bucket is a range that can hold one or more elements,

For example, there is a non-integer sequence as follows:

4.5， 0.84， 3.25， 2.18， 0.5

The first step is to create buckets and determine the range of each bucket,

In this case, the number of buckets created is equal to the number of elements in the original sequence. Except that the last bucket contains only the maximum value of the sequence, the interval of each preceding bucket is determined in proportion

Interval span = (Max – min)/(number of buckets – 1)

The second step is to iterate through the original array, placing the elements into each bucket

Third, sort the elements in each bucket individually

Step 4, iterate through all buckets and output all elements

The implementation code

function bucketSort(arr:Array<number>) { // 1. Let Max = arr[0]; let Max = arr[0]; let min = arr[0]; for (let index = 0; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } const d = max - min; Const bucketNum = arr.length; / * small pit: Let bucketList = new Array(bucketNum).fill([]) */ let bucketList = new Array(bucketNum) for (let index = 0; index < bucketList.length; index++) { bucketList[index] = [] } // 3. Let area = d/(bucketNum - 1); for (let index = 0; index < arr.length; index++) { let num = Math.floor((arr[index] - min)/area); BucketList [num].push(arr[index])} /* bucketList[num].push(arr[index])} (element -min)/area = the number of buckets in the list, which should be rounded up from 0, so math.floor 2.bucketnum -1: Since (maximum value -min)/area must be the last bucket and an integer, that is:  d = max - min area = d/num result = (max - min)/area = (max - min)/d * num = (max - min)/(max - min) * num result === D /(num - 1) */ / 4 For (let index = 0; index < bucketList.length; index++) { bucketList[index] = bucketList[index].sort((a:number, Return bucketList.flat()} function main() {let arr = [4.12, 6.412, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09, 10]; console.log(bucketSort(arr)) }; main();Copy the code

summary

Time complexity:

1. Calculate the maximum and minimum value of the sequence, and the computation quantity is N

2. Create an empty bucket. The operation amount is N

3. Allocate the elements of the original array to buckets with n operation

4. Sort within each bucket. In the case that elements are evenly distributed, the sum of operations in all buckets is N

5. Output sorted sequence with n computation

So the time is order n.

The space complexity is order n.

Question:

1. Increase the number of buckets as much as possible for performance when extra space is sufficient

2. Bucket sorting performance is not absolutely stable. If the distribution of elements is very uneven, in extreme cases, there are n-1 elements in one bucket and 1 element in the last bucket, the time complexity will degenerate to O(nlogn), and many empty buckets are created for nothing

Summary from: the journey of cartoon algorithm xiao Grey algorithm