解题思路 or 实现原理

基数排序是一种非比较型整数排序算法, 其原理是将整数按位数切割成不同的数字, 然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数, 所以基数排序也不是只能使用于整数。

算法步骤

基数排序有两种方法:

这三种排序算法都利用了桶的概念, 但对桶的使用方法上有明显差异:

• 基数排序: 根据键值的每位数字来分配桶;
• 计数排序: 每个桶只存储单一键值;
• 桶排序: 每个桶存储一定范围的数值;

实现代码

/*
 * @Author: Rainy
 * @Date: 2019-11-14 19:25:01
 * @LastEditors  : Rainy
 * @LastEditTime : 2019-12-29 11:15:28
 */

import { NumberArrayMap } from 'types';
import { insertionSort } from '../insertionSort';

export function bucketSort(
  arr: NumberArrayMap,
  bucketSize?: number,
): NumberArrayMap {
  if (arr.length === 0) {
    return arr;
  }

  let i;
  let minValue = arr[0];
  let maxValue = arr[0];
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }

  let DEFAULT_BUCKET_SIZE: number = 5;
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  let bucketCount: number = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  for (i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }

  arr.length = 0;
  for (i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }

  return arr;
}

参考

radixSort (opens new window)