How to implement counting sorting in JS

This article mainly introduces the counting sorting and radix sorting algorithms implemented by JS, and briefly analyzes the principles and JS implementation techniques of counting sorting and radix sorting in the form of examples. Friends in need can refer to this article

The example describes the counting sorting and radix sorting algorithms implemented in JS. Share it with everyone for your reference, the details are as follows:

Counting sort

Counting sort is a simple bucket sort, one bucket represents one in the array The number of occurrences of a number, so an auxiliary array is required that is as large as the numerical range of the array. It is generally used for sorting with a range less than 100. The time complexity is O(n), and the space complexity is the numerical range of the array.

/**
 * 范围在 start - end 之间的排序
 * 计数排序需要辅助数组，该辅助数组的长度是待排序数组的范围，所以一般用作范围小于100的排序
 */
function countSort(arr, start, end) {
  var len = arr.length;
  // 桶数组
  var suportArr = new Array(end - start + 1);
  // 结果数组
  var resArr = new Array(len);
  // 初始化桶数组
  for (i = 0; i < suportArr.length; i++) {
    suportArr[i] = 0;
  }
  // 待排序数组中的数组出现，在桶子对应位置+1代表这个数出现的个数+1了
  for (let i = 0; i < len; i++) {
    suportArr[arr[i]]++;
  }
   // 从第1项开始，桶数组加上前一个桶的个数，现在辅助数组的意义变成了每一项的排名了。
  for (let i = 1; i < suportArr.length; i++) {
    suportArr[i] += suportArr[i - 1];
  }
  // 根据辅助数组的排名，从后往前赋值
  for (let i = len - 1; i >= 0; i--) {
    resArr[suportArr[arr[i]] - 1] = arr[i];
    suportArr[arr[i]]--;
  }
  return resArr;
}

Radix sorting

Radix sorting is a multi-lay bucket sorting

var radix = 16; // 基数，可以为任何数，越大趟数越小，但是桶数越多，最好根据最大数字进行定义。
function _roundSort(arr, round, radix) {
  var buckets = new Array(radix);
  for (let i = 0; i < radix; i++) {
    buckets[i] = [];
  }
  // 将数组中的数放进对应的桶子中
  for (let i = 0; i < arr.length; i++) {
    let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;
    buckets[remainder].push(arr[i]);
  }
  // 将数组重新根据桶子进行排序
  var index = 0;
  for (let i = 0; i < buckets.length; i++) {
    for (let j = 0; j < buckets[i].length; j++) {
      arr[index++] = buckets[i][j];
    }
  }
}
function radixSort(arr, round) {
  for (let i = 1; i <= round; i++) {
    _roundSort(arr, i, radix);
  }
  return arr;
}
console.log(radixSort([10,5,5,50,0,155,4622,5,1,4,2154], 4));

The above is what I compiled for everyone, I hope it will be helpful to everyone in the future.

Related articles:

How to install nvm on Mac (detailed tutorial)

How to implement the time function in the WeChat applet

Exploration on generated code in webpack

The above is the detailed content of How to implement counting sorting in JS. For more information, please follow other related articles on the PHP Chinese website!