升序排列数组

  1. function radixSort(arr) {
  2.   const radixBase = 10;
  3.   const buckets = [];
  5.   for (let i = 0; i < radixBase; i++) {
  6.     buckets[i] = [];
  7.   }
  9.   let maxValue = Math.max(...arr);
  10.   let digits = 0;
  12.   do {
  13.     digits++;
  14.     maxValue = Math.floor(maxValue / radixBase);
  15.   } while (maxValue !== 0);
  17.   let placement = 1;
  19.   for (let i = 0; i < digits; i++) {
  20.     for (let i = 0; i < arr.length; i++) {
  21.       let temp = arr[i] / placement;
  22.       buckets[Math.floor(temp % radixBase)].push(arr[i]);
  23.     }
  25.     let p = 0;
  26.     for (let j = 0; j < radixBase; j++) {
  27.       const buck = buckets[j];
  28.       while (buck.length) {
  29.         arr[p] = buck.shift();
  30.         p++;
  31.       }
  32.     }
  34.     placement *= 10;
  35.   }
  37.   return arr;
  38. }

算法测试

  1. console.log(radixSort([12, 2, 1, 28, 27, 56, 123]));
  2. // [ 1,  2,  12, 27, 28, 56, 123 ]
  4. console.log(radixSort([412, 7, 102, 55, 3333, 1, 99, 100]));
  5. // [ 1, 7, 55, 99, 100, 102, 412, 3333 ]
  7. console.log(radixSort([12, 2, 0, 4, 3, 8]));
  8. // [ 0, 2, 3, 4, 8, 12 ]