So implementieren Sie die Zählsortierung in JS

In diesem Artikel werden hauptsächlich die von JS implementierten Zählsortierungs- und Radixsortierungsalgorithmen vorgestellt. Er analysiert kurz die Prinzipien und JS-Implementierungstechniken der Zählsortierung und Radixsortierung in Form von Beispielen

Das Beispiel beschreibt die in JS implementierten Zählsortierungs- und Basissortierungsalgorithmen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Zählsortierung

Zählsortierung ist eine einfache Eimersortierung, ein Eimer stellt eins im Array dar. Die Anzahl der Vorkommen einer Zahl, daher ist ein Hilfsarray erforderlich, das so groß ist wie der numerische Bereich des Arrays. Es wird im Allgemeinen zum Sortieren mit einem Bereich von weniger als 100 verwendet. Die zeitliche Komplexität beträgt O( n) und die Raumkomplexität ist der numerische Bereich des Arrays.

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

Radix-Sortierung ist eine Multi-Lay-Bucket-Sortierung

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

Das Obige ist das, wofür ich kompiliert habe Ich hoffe, dass es in Zukunft für alle hilfreich sein wird.

Verwandte Artikel:

So installieren Sie nvm auf einem Mac (ausführliche Anleitung)

So implementieren Sie die Zeitfunktion im WeChat-Applet

Erkunden des generierten Codes im Webpack

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Zählsortierung in JS. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!