基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法:
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
- 基数排序:根据键值的每位数字来分配桶;
- 计数排序:每个桶只存储单一键值;
- 桶排序:每个桶存储一定范围的数值;
2. LSD 基数排序动图演示

3. JavaScript 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| var counter = []; function radixSort(arr, maxDigit) { var mod = 10; var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]!=null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } } } return arr; }
|
4. Java 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
|
public class RadixSort implements IArraySort {
@Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr); return radixSort(arr, maxDigit); }
private int getMaxDigit(int[] arr) { int maxValue = getMaxValue(arr); return getNumLenght(maxValue); }
private int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; }
protected int getNumLenght(long num) { if (num == 0) { return 1; } int lenght = 0; for (long temp = num; temp != 0; temp /= 10) { lenght++; } return lenght; }
private int[] radixSort(int[] arr, int maxDigit) { int mod = 10; int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) { int bucket = ((arr[j] % mod) / dev) + mod; counter[bucket] = arrayAppend(counter[bucket], arr[j]); }
int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { arr[pos++] = value; } } }
return arr; }
private int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; } }
|
5. PHP 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| function radixSort($arr, $maxDigit = null) { if ($maxDigit === null) { $maxDigit = max($arr); } $counter = []; for ($i = 0; $i < $maxDigit; $i++) { for ($j = 0; $j < count($arr); $j++) { preg_match_all('/\d/', (string) $arr[$j], $matches); $numArr = $matches[0]; $lenTmp = count($numArr); $bucket = array_key_exists($lenTmp - $i - 1, $numArr) ? intval($numArr[$lenTmp - $i - 1]) : 0; if (!array_key_exists($bucket, $counter)) { $counter[$bucket] = []; } $counter[$bucket][] = $arr[$j]; } $pos = 0; for ($j = 0; $j < count($counter); $j++) { $value = null; if ($counter[$j] !== null) { while (($value = array_shift($counter[$j])) !== null) { $arr[$pos++] = $value; } } } }
return $arr; }
|