排序算法-基数排序

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

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

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异案例看大家发的：

基数排序：根据键值的每位数字来分配桶；

计数排序：每个桶只存储单一键值；

桶排序：每个桶存储一定范围的数值；

2. LSD 基数排序动图演示

3. JavaScript 代码实现

//LSD Radix Sort 

var counter = []; 
function radixSort(arr, **xDigit) { 
var mod = 10; 
var dev = 1; 
for (var i = 0; i < **xDigit; 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. python 代码实现

def radix(arr): 


digit = 0 
**x_digit = 1 
**x_value = **x(arr) 
#找出列表中较大的位数 
while 10****x_digit < **x_value: 
**x_digit = **x_digit + 1 

while digit < **x_digit: 
temp = [[] for i in range(10)] 
for i in arr: 
#求出每一个元素的个、十、百位的值 
t = int((i/10**digit)%10) 
temp[t].append(i) 

coll = [] 
for bucket in temp: 
for i in bucket: 
coll.append(i) 

arr = coll 
digit = digit + 1 

return arr

5. Java 代码实现

/** 

* 基数排序 
* 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9 
*/ 
public class RadixSort implements IArraySort { 

@Override 
public int[] sort(int[] sourceArray) throws Exception { 
// 对 arr 进行拷贝，不改变参数内容 
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); 

int **xDigit = getMaxDigit(arr); 
return radixSort(arr, **xDigit); 
} 

/** 
* 获取较高位数 
*/ 
private int getMaxDigit(int[] arr) { 
int **xValue = getMaxValue(arr); 
return getNumLenght(**xValue); 
} 

private int getMaxValue(int[] arr) { 
int **xValue = arr[0]; 
for (int value : arr) { 
if (**xValue < value) { 
**xValue = value; 
} 
} 
return **xValue; 
} 

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 **xDigit) { 
int mod = 10; 
int dev = 1; 

for (int i = 0; i < **xDigit; i++, dev *= 10, mod *= 10) { 
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 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; 
} 

/** 
* 自动扩容，并保存数据 
* 
* @param arr 
* @param value 
*/ 
private int[] arrayAppend(int[] arr, int value) { 
arr = Arrays.copyOf(arr, arr.length + 1); 
arr[arr.length - 1] = value; 
return arr; 
} 
}

6. PHP 代码实现

function radixSort($arr, $**xDigit = null) 

{ 
if ($**xDigit === null) { 
$**xDigit = **x($arr); 
} 
$counter = []; 
for ($i = 0; $i < $**xDigit; $i++) { 
for ($j = 0; $j < count($arr); $j++) { 
preg_**tch_all('/\d/', (string) $arr[$j], $**tches); 
$numArr = $**tches[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; 
}