이 글은 주로 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!