Exemples d'algorithmes de tri par comptage et de tri par base implémentés dans les compétences JS_javascript

Cet article présente principalement les algorithmes de tri par comptage et de tri par base implémentés par JS Il analyse brièvement les principes du tri par comptage et du tri par base et les techniques de mise en œuvre de JS sous la forme. d'exemples JSLes amis intéressés peuvent venir jeter un oeil !

Les exemples de cet article décrivent les algorithmes de tri par comptage et de tri par base implémentés par JS. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Tri par comptage

Le tri par comptage est un simple tri par seau, un seau représente Le nombre d'occurrences d'un nombre dans le tableau , donc un tableau auxiliaire est requis qui est aussi grand que la plage du numéro du tableau. Il est généralement utilisé pour le tri avec une plage inférieure à 100. la complexité temporelle est O(n) et la complexité spatiale est le numéro de la portée du tableau.

/**
 * 范围在 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;
}

Le tri Radix

Le tri Radix est Tri des seaux à positions multiples

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));

Ce qui précède est tout le contenu de cet article, j'espère qu'il pourra être utile pour les étudiants !

Recommandations associées :

Comment implémenter les bases des compteurs en JavaScript

Réponses aux questions sur la dénomination des cas de chameaux et JS

Comment utiliser l'événement bouillonnant de JS

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!