JS實現(xiàn)基數排序的示例代碼

更新時間：2023年12月04日 15:49:31 作者：CreatorRay

基數排序是一種根據數字位數的值,對整數進行排序的算法,本文主要介紹了JS實現(xiàn)基數排序的示例代碼,具有一定的參考價值,感興趣的可以了解一下

什么是基數排序

基數排序是一種根據數字位數的值，對整數進行排序的算法。它將整數按照位數切割成不同的數字，然后按照每個位數分別比較?；鶖蹬判虻暮诵乃枷胧菑牡臀坏礁呶唬瑢γ恳晃贿M行排序，最終得到有序序列。

如何實現(xiàn)基數排序

以下是一個基于 JavaScript 的基數排序實現(xiàn)：

// 獲取數字的指定位數上的數字
function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

// 獲取數字的位數
function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

// 獲取數字中最大位數
function mostDigits(nums) {
  let maxDigits = 0;
  for (let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

// 基數排序函數
function radixSort(nums) {
  const maxDigits = mostDigits(nums);

  for (let k = 0; k < maxDigits; k++) {
    const buckets = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < nums.length; i++) {
      const digit = getDigit(nums[i], k);
      buckets[digit].push(nums[i]);
    }

    nums = [].concat(...buckets);
  }

  return nums;
}

// 示例
const unsortedArray = [170, 45, 75, 90, 802, 24, 2, 66];
const sortedArray = radixSort(unsortedArray);
console.log(sortedArray); // 輸出 [2, 24, 45, 66, 75, 90, 170, 802]