Detailed explanation of bucket sorting in JavaScript

This article talks about bucket sorting in JavaScript. If you don’t know about bucket sorting in JavaScript or are interested in bucket sorting in JavaScript, then let’s take a look at this article. Okay, let’s cut the nonsense and get to the point

Bucket sorting is an upgraded version of counting sorting. It makes use of the mapping relationship of function. The key to efficiency lies in the determination of this mapping function.

In order to make bucket sorting more efficient, we need to do these two things:

1. When there is sufficient extra space, try to increase the number of buckets

2. The mapping function used can evenly distribute the input N data into K buckets

At the same time, for the sorting of elements in the bucket, what kind of comparison should be selected? Sorting algorithms have a critical impact on performance.

When is it fastest?

#When the input data can be evenly distributed to each bucket

When is it slowest

When the input data is allocated to the same bucket

Bucket sorting JavaScript code implementation:

function bucketSort(arr, bucketSize) {  
    if (arr.length === 0) {  
      return arr;  
    }  
  
    var i;  
    var minValue = arr[0];  
    var maxValue = arr[0];  
    for (i = 1; i < arr.length; i++) {  
      if (arr[i] < minValue) {  
          minValue = arr[i];                //输入数据的最小值  
      } else if (arr[i] > maxValue) {  
          maxValue = arr[i];                //输入数据的最大值  
      }  
    }  
  
    //桶的初始化  
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5  
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;  
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;     
    var buckets = new Array(bucketCount);  
    for (i = 0; i < buckets.length; i++) {  
        buckets[i] = [];  
    }  
  
    //利用映射函数将数据分配到各个桶中  
    for (i = 0; i < arr.length; i++) {  
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);  
    }  
  
    arr.length = 0;  
    for (i = 0; i < buckets.length; i++) {  
        insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序  
        for (var j = 0; j < buckets[i].length; j++) {  
            arr.push(buckets[i][j]);                        
        }  
    }  
  
    return arr;}

The above is all the content of this article. If you don’t know much about it, you can easily master both sides by yourself!

Related recommendations:
PHP implementation of bucket sorting algorithm example sharing

The above is the detailed content of Detailed explanation of bucket sorting in JavaScript. For more information, please follow other related articles on the PHP Chinese website!