定義
基數(shù)排序（英語：Radix Sort）是一種非比較型整數(shù)排序算法缠犀，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較粥鞋。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
基數(shù)排序過程
算法步驟
- 將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度贱勃，數(shù)位較短的數(shù)前面補零。
- 然后谤逼，從最低位開始贵扰，依次進行一次排序。
- 這樣從最低位排序一直到最高位排序完成以后流部，數(shù)列就變成一個有序序列戚绕。
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始枝冀，而MSD則相反舞丛，由鍵值的最左邊開始。
注意本次演示采用LSD的方式實現(xiàn)
代碼實現(xiàn)（java）
/**
*
* Description: 基數(shù)排序的簡單實現(xiàn)果漾，目前只能排序正整數(shù)
* @param: @param nums
* @param: @return
* @return: int[]
* @throws
*/
public static int[] radixSort(int[] nums)
{
int BASE = 10; // 整數(shù)基數(shù)
int len = nums.length;
int[] buffer = new int[len];
int maxValue = nums[0], exp = 1;
// 找出nums數(shù)組中最大的數(shù)
for (int i = 1; i < len; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
}
}
while (maxValue / exp > 0) {
int[] bucket = new int[BASE];
for (int i = 0; i < bucket.length; i++) {
bucket[i] = 0;
}
// 從數(shù)的低位開始進行桶排序
for (int i = 0; i < len; i++) {
bucket[(nums[i] / exp) % BASE]++;
}
// 按照當前位給nums排序球切，確定各個數(shù)對應的大概位置buket[(nums[i] / exp) % BASE]的值
// 即為新位置的下標
for (int i = 1; i < BASE; i++) {
bucket[i] += bucket[i - 1];
}
// 按當前位進行排序存入到新數(shù)組
for (int i = len - 1; i >= 0; i--) {
int index = (nums[i] / exp) % BASE;
buffer[--bucket[(nums[i] / exp) % BASE]] = nums[i];
}
for (int i = 0; i < len; i++) {
nums[i] = buffer[i];
}
exp *= BASE;
}
return nums;
}
