Count sorting

The diagram below:

Primitive array: that is, the array to be sorted count array: intermediate array required to implement sorting requirements

We create it by finding the largest element in the original array as the length of the count array and then we start counting

Finally, the count element group is traversed by the cycle to obtain elements by subscript, which can be sorted

Post code ~

function countSort(arr){
    let maxValue = 0;
    for(let i = 0; i< arr.length; i++){
        if(maxValue < arr[i]){
            maxValue = arr[i] // Get the maximum value}}The array is created with +1 because the array starts at 0
    let bucket = new Array(maxValue + 1) 
    for(let i = 0; i < arr.length; i++){
        let num = arr[i]
        if(bucket[num] ==null){
            bucket[num] = 1
        }else{
            bucket[num] += 1}}let arrCurrIndex = 0;
    // Iterate over the count element group
    for(let i=0; i<bucket.length; i++){Loop over a single element because the count of the same number can be greater than 1
        while(bucket[i]>0) {let num =i 
            arr[arrCurrIndex++] = num;
            bucket[i] -= 1}}}Copy the code

Bucket sort

Bucket sort is a kind of counting sort derived from counting sort is a single count of a single element so bucket sort is a single element by placing the size of the bucket, the size of the chase element comparison into the bucket, the bucket sort code ~

function bucketSort(arr,bucketCount){
  //bucketCount Specifies the number of elements in each bucket
  let result = [],
  minValue = arr[0],
  maxValue = arr[0];

  for(let i = 0; i < arr.length; i++){
    if(arr[i] < minValue){
      minValue = arr[i]
    }
    if(arr[i] > maxValue){
      maxValue = arr[i]
    }
  }
  // bucketSize specifies the entire bucketSize
  let bucketSize = Math.floor((maxValue - minValue)/ bucketCount) + 1
  // Create an array of buckets.
  let bucket = new Array(bucketSize)
  for(let i = 0; i<bucket.length; i++){
    bucket[i] = []
  }
    // Classify each element into buckets (i.e. a bucket should contain buckerCount elements)
  for(let i = 0; i<arr.length; i++){
    bucket[Math.floor((arr[i]-minValue)/bucketCount)].push(arr[i])
  }

  for(let i = 0; i<bucket.length; i++){// Insert sort for each bucket
    insetionSort(bucket[i])
    for(let j = 0; j < bucket[i].length; j++){
      result.push(bucket[i][j])
    }
  }
}
function insetionSort(arr){
  let len = arr.length,prev,current;
  for(let i = 1; i < len ; i++){ 
    prev = i - 1
    current = arr[i]
    while( prev >=0 && arr[prev]>current){
      arr[prev+1] = arr[prev]
      prev -- ;
    }
    arr[prev+1] = current
  }
}
Copy the code