基数排序:
它的基本思想是:类似于创建一个二维的链表(第一层链表为0-9号),首先看每个数的个位,如果为0放入0号链表,为1放入1号链表……再对十位,百位排……。每躺排序后吧链表遍历一遍放入传入的arr中,经过几轮之后就排序完成。简单来说就是先对个位排序,在对十位排序,再对百位排序,以此类推。
排序方法:
比如我们要排序 arr{135,242,192,93,345,11,24,19}
第一步:收集个位数
1.把每个数对10求余得到个位数,然后根据个位数放入0-9号链表:
链表: 0 1 2 3 4 5 6 7 8 9
{ [] [11] [242,192] [93] [24] [135,345] [] [] [] [19] }
根据遍历,取出元素放入arr数组中得到:
{11,242,192,93,24,135,345,19}
2.进行第二轮对100求余再除10得到十位的数字,进行对十位排序:
链表: 0 1 2 3 4 5 6 7 8 9
{ [] [11,19] [24] [135] [242,345] [] [] [] [] [192,93] }
3.进行第三轮排序,对1000求余,再除100得到百位数字,进行百位排序:
链表: 0 1 2 3 4 5 6 7 8 9
{ [11,19,24,93] [135,192] [242] [345] [] [] [] [] [] [] }
遍历得到: {11,19,24,93,135,192,242,345}
大家发现没有,当对最大的位数排序完后,数组arr就已经排序成功了,这就是基数排序。
下面的图就是这个例子:(图中第一躺个位19应该在9号链表)
由于这个方法只能对正数进行排序,如果存在负数,我们就把负数和正数分开成两个数组,然后排序之后合并起来就可以,具体见代码,加入了详细注释。
import java.util.ArrayList;
public class BasicSort {
public static void basicSort(int[] arr) {
//获取最大值
int max = 0;
for (int i = 0; i < arr.length; i++) {
if(max < arr[i]) {
max = arr[i];
}
}
//获取最大位数
int count = 0;
while (max > 0) {
max /= 10;
count++;
}
ArrayList<ArrayList> queue = new ArrayList<ArrayList>();
//i是位数,在每个位数上构造一个数组
for (int i = 0; i < 10; i++) {
queue.add(new ArrayList());
}
//分配数组
for (int i = 0; i < count; i++) {//遍历各个位
for (int j = 0 ; j < arr.length; j++) {//遍历arr数组
//获取对应位的值,如果第一轮就得到各位的值,第二轮就得到百位的值
int x = arr[j] % (int)(Math.pow(10, i + 1)) / (int)(Math.pow(10, i));
queue.get(x).add(arr[j]);//取第x组把当前元素添加进去
}
//形成新的arr数组
int count2 = 0;
for (int j = 0; j < 10; j++) {
while (queue.get(j).size() > 0) {
ArrayList<Integer> q = queue.get(j);
arr[count2] = q.get(0);
q.remove(0);
count2++;
}
}
}
}
public static void sort(int[] arr) {
//设置两个数组接受正负数
int[] arr1 = new int[arr.length];
int[] arr2 = new int[arr.length];
//正负数计数器
int count1 = 0;
int count2 = 0;
//正数放入arr1,负数把他变正放入arr2
for (int i = 0; i < arr.length; i++) {
if(0 <= arr[i]) {
arr1[count1] = arr[i];
count1++;
}
else {
arr2[count2] = -1 * arr[i];
count2++;
}
}
//对负数排序,然后反向存入arr的0——count2中
basicSort(arr2);
for(int i = 0; i < count2 ; i++) {
arr[i] = -1 * arr2[arr2.length - 1 - i];
}
//对正数排序,吧正数从count2存入arr中
basicSort(arr1);
for(int i = count2; i < count1 + count2 ; i++) {
arr[i] = arr1[i];
}
}
public static void main(String[] args) {
int[] arr = {136,-37,27,48,1,-2,0};
sort(arr);
for (int n:arr) {
System.out.print(" " + n);
}
}
}