introduce

Bucket sorting is the simplest sorting algorithm. For example, in a scenario where data ranges from 0 to N, we assume that n+1 buckets are used for sorting, and put the data to be sorted into the corresponding bucket serial number one by one. That is, data 3 is put into the third bucket, and data 67 is put into the 67th bucket. Finally find the data in the bucket from start to end (ascending) or from end to end (descending).

example

Given an array to sort [77, 6, 37, 96, 34, 6,14], the js implementation of bucket sort is as follows (ascending order) :

function sort(arr){
   var buckets = [], / / auxiliary barrels
       result = []; // Save the result

   // Put the data to be sorted into buckets one by one
   arr.forEach(function(item){
       // A bucket can hold more than one number
       if(buckets[item]) buckets[item].push(item);
       else buckets[item] = [item]; 
   });

   // Output the bucket from start to end, iterating n times
   buckets.forEach(function(item){
       if(item) result = result.concat(item);
   })
   return result;
}

var arr = [77.6.37.96.34.6.14];
console.log(sort(arr)); // =>[6, 6, 14, 34, 37, 77, 96]
Copy the code

Time complexity

Large O order f(n) = n + n = 2n, so the time complexity is O(n). While the time consumption is ok, bucket sorting has a fatal drawback: it wastes space.

Thanks for reading! Welcome to pay attention! Continuously updated…