基数排序

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

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法:

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

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

2. 算法分析

基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要O(n)的时间复杂度,而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n) ,当然d要远远小于n,因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k),其中k为桶的数量。一般来说n>>k,因此额外空间需要大概n个左右。

3. 算法步骤

  1. 取得数组中的最大数,并取得位数;
  2. arr为原始数组,从最低位开始取每个位组成radix数组;
  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点);

4. LSD 基数排序动图演示

动图演示

5. 代码实现

1. JavaScript 代码实现

  1. //LSD Radix Sort
  2. var counter = [];
  3. function radixSort(arr, maxDigit) {
  4. var mod = 10;
  5. var dev = 1;
  6. for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  7. for(var j = 0; j < arr.length; j++) {
  8. var bucket = parseInt((arr[j] % mod) / dev);
  9. if(counter[bucket]==null) {
  10. counter[bucket] = [];
  11. }
  12. counter[bucket].push(arr[j]);
  13. }
  14. var pos = 0;
  15. for(var j = 0; j < counter.length; j++) {
  16. var value = null;
  17. if(counter[j]!=null) {
  18. while ((value = counter[j].shift()) != null) {
  19. arr[pos++] = value;
  20. }
  21. }
  22. }
  23. }
  24. return arr;
  25. }

2. Java 代码实现

  1. /**
  2. * 基数排序
  3. * 考虑负数的情况还可以参考: https://code.i-harness.com/zh-CN/q/e98fa9
  4. */
  5. public class RadixSort implements IArraySort {
  6. @Override
  7. public int[] sort(int[] sourceArray) throws Exception {
  8. // 对 arr 进行拷贝,不改变参数内容
  9. int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  10. int maxDigit = getMaxDigit(arr);
  11. return radixSort(arr, maxDigit);
  12. }
  13. /**
  14. * 获取最高位数
  15. */
  16. private int getMaxDigit(int[] arr) {
  17. int maxValue = getMaxValue(arr);
  18. return getNumLenght(maxValue);
  19. }
  20. private int getMaxValue(int[] arr) {
  21. int maxValue = arr[0];
  22. for (int value : arr) {
  23. if (maxValue < value) {
  24. maxValue = value;
  25. }
  26. }
  27. return maxValue;
  28. }
  29. protected int getNumLenght(long num) {
  30. if (num == 0) {
  31. return 1;
  32. }
  33. int lenght = 0;
  34. for (long temp = num; temp != 0; temp /= 10) {
  35. lenght++;
  36. }
  37. return lenght;
  38. }
  39. private int[] radixSort(int[] arr, int maxDigit) {
  40. int mod = 10;
  41. int dev = 1;
  42. for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  43. // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
  44. int[][] counter = new int[mod * 2][0];
  45. for (int j = 0; j < arr.length; j++) {
  46. int bucket = ((arr[j] % mod) / dev) + mod;
  47. counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  48. }
  49. int pos = 0;
  50. for (int[] bucket : counter) {
  51. for (int value : bucket) {
  52. arr[pos++] = value;
  53. }
  54. }
  55. }
  56. return arr;
  57. }
  58. /**
  59. * 自动扩容,并保存数据
  60. *
  61. * @param arr
  62. * @param value
  63. */
  64. private int[] arrayAppend(int[] arr, int value) {
  65. arr = Arrays.copyOf(arr, arr.length + 1);
  66. arr[arr.length - 1] = value;
  67. return arr;
  68. }
  69. }

3. PHP 代码实现

  1. function radixSort($arr, $maxDigit = null)
  2. {
  3. if ($maxDigit === null) {
  4. $maxDigit = max($arr);
  5. }
  6. $counter = [];
  7. for ($i = 0; $i < $maxDigit; $i++) {
  8. for ($j = 0; $j < count($arr); $j++) {
  9. preg_match_all('/\d/', (string) $arr[$j], $matches);
  10. $numArr = $matches[0];
  11. $lenTmp = count($numArr);
  12. $bucket = array_key_exists($lenTmp - $i - 1, $numArr)
  13. ? intval($numArr[$lenTmp - $i - 1])
  14. : 0;
  15. if (!array_key_exists($bucket, $counter)) {
  16. $counter[$bucket] = [];
  17. }
  18. $counter[$bucket][] = $arr[$j];
  19. }
  20. $pos = 0;
  21. for ($j = 0; $j < count($counter); $j++) {
  22. $value = null;
  23. if ($counter[$j] !== null) {
  24. while (($value = array_shift($counter[$j])) !== null) {
  25. $arr[$pos++] = $value;
  26. }
  27. }
  28. }
  29. }
  30. return $arr;
  31. }