JS에서 계산 정렬을 구현하는 방법

이 글은 주로 JS에서 구현한 카운팅 정렬과 기수 정렬 알고리즘을 소개합니다. 카운팅 정렬과 기수 정렬의 원리와 JS 구현 기술을 예제 형식으로 간략하게 분석합니다. 기사에서는 JS 계산 정렬 및 기수 정렬 알고리즘의 구현을 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

Counting sortCounting sort는 간단한 버킷 정렬이므로 버킷은 배열에서 숫자가 나타나는 횟수를 나타냅니다. 보조 배열은 일반적으로 100 미만의 범위로 정렬하는 데 사용됩니다. 시간 복잡도는 O(n)이고 공간 복잡도는 배열의 숫자 범위입니다.

/**
 * 范围在 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 정렬Radix 정렬은 다중 계층 버킷 정렬입니다.

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

위 내용은 제가 모든 사람을 위해 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.

관련 기사:

Mac에 nvm을 설치하는 방법(자세한 튜토리얼)

WeChat 애플릿에서 시간 기능을 구현하는 방법

webpack에서 생성된 코드 탐색

위 내용은 JS에서 계산 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!