第一个点
这里有几个比较有意思的点，首先是我们要知道最大的数字的位数，以便知道我们要比到多少位。
要做到这一点，首先要找出最大值，这个简单**int **max = arr[0];<br />**for **(**int **i = 0;i < arr.**length**;i++){<br /> **if **(arr[i] > max){<br /> max = arr[i];<br /> }<br />}
然后在最大值后面拼接一个空字符串，使之变成字符串求长度**int **maxLength = (max+**""**).length();这样一来我们就得到了一共要比较多少位
第二个点
接下来要取出个位、百位、千位……的数分别比较，个位数可以通过arr[j] % 10得到，百位是arr[j] /10 % 10,千位是arr[j] /100 % 10，这个可以通过循环的步长来控制，所以总代码如下
`public static void radixSort(int[] arr){
//得到数组中最大的位数
int max = arr[0];
for (int i = 0;i < arr.length;i++){
if (arr[i] > max){
max = arr[i];
}
}
//得到最大的是几位数
int maxLength = (max+“”).length();
_//定义一个二维数组，表示10个桶，每个桶就是一个一维数组<br /> //为了防止在放入数据的时候出现数据溢出，则每一个桶的大小为arr.length<br /> //经典空间换时间<br /> _**int**[][] bucket = **new int**[10][arr.**length**];_//定义一个一维数组来记录各个桶每次放入数据的个数<br /> _**int**[] bucketNum = **new int**[10];**for **(**int **i = 0 , n = 1;i<maxLength;i++, n*=10){<br /> _//针对每个元素对应的位进行排序处理，第一轮个位，第二轮百位……<br /> _**for **(**int **j = 0;j < arr.**length**;j++){<br /> _//取出每个元素对应位的值<br /> _**int **unit = arr[j] /n % 10;<br /> _//放入到对应的桶中<br /> _bucket[unit][bucketNum[unit]] = arr[j];_//bucketNum[unit]，一开始是0<br /> _bucketNum[unit]++;_//因为个数和索引数目总是差一，所以后++让二者保持一致<br /> _}<br /> _//按照这个桶的顺序取出数据（一维数组的下标依次取出数据，放入原来的数组）<br /> _**int **index = 0;<br /> _//遍历每一个桶，并将桶中的数据放入到原数组<br /> _**for **(**int **k = 0;k < bucket.**length**;k++){<br /> _//判断桶中有无数据<br /> _**if**(bucketNum[k] != 0){<br /> _//循环该桶<br /> _**for **(**int **l = 0;l < bucketNum[k];l++){<br /> arr[index] = bucket[k][l];<br /> index++;<br /> }<br /> }<br /> _//循环完每个桶之后，需要清零（这里并不是真的把数据删除，只是单纯改变指针）<br /> _bucketNum[k] = 0;<br /> }<br /> }`
注意事项
数据量不多时，这个算法非常快，当是当数据量达到八千万时，需要3.3个g的堆内存，可能内存不足
这里还没有实现队负数的排序，负数思路如下：
先取绝对值进行排序，然后赋值时再进行反转即可
若有收获，就点个赞吧
0 人点赞
