基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序
算法复杂度：O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。稳定
算法思想：
- 取得最大数的位数有多少,建立二维数组
- 循环位数次，每次通过位数进行筛选，结束后按0-9顺序，进行输出 a. 当进行十位数筛选时，由于个位数十位为0，所以都在0的二维中，所以输出时先输出0，所以进行排序，高位依然如此
针对负数以及小数：
- 针对负数，所有数字加一最小负数的绝对值，排序完成后再减掉
- 针对小数，所有数字乘以10的小数位次方，排序完成后再除掉
import java.util.ArrayList;
/**
* 基数排序
* @author Naah
*
*/
public class BasicSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array= {2,2,4,66,56,32,3,34,54,22,67,77,23,5353,3444,55,6,77,88};
BasicSort sort=new BasicSort();
sort.basicSort(array);
for (int i : array) {
System.out.println(i);
}
}
/**
* 基数排序算法
* 通过数字的位数进行排序
* @param array 数组
*/
public void basicSort(int[] array) {
//最大值变量
int max=0;
//获取最大值
for (int i = 0; i < array.length; i++) {
if (array[i]>max) {
max=array[i];
}
}
//最大值位数
int bits=0;
//遍历获取最大值位数
while (max>0) {
bits++;
max/=10;
}
//创建基数二维数组
ArrayList<ArrayList> list=new ArrayList<ArrayList>();
//每位数都是0-9，所以一共添加10个ArrayList到list中
for (int i = 0; i < 10; i++) {
list.add(new ArrayList<Integer>());
}
//每位循环一次
for (int i = 0; i < bits; i++) {
//每次循环一边数组，进行数组排列
for (int j = 0; j < array.length; j++) {
//取得该位的数字，（先用大一位取余，然后再取整）
//i=0，取个位，i=1，取十位，i=2，取百位
int x=(int) (array[j]%Math.pow(10, i+1)/Math.pow(10, i));
//取出位数对应的数组
ArrayList<Integer> eleList=list.get(x);
//将该数添加到该数组
eleList.add(array[j]);
}
//将排列后的数组进行归并
//数组引用
int count=0;
//循环所有位数
for (int j = 0; j < 10; j++) {
//当位数组有值时，循环
while (list.get(j).size()>0) {
///取出该位数组
ArrayList<Integer> eleList=list.get(j);
//将位数组第一个数填入数组中
array[count++]=eleList.get(0);
//移除位数组中第一个值/
eleList.remove(0);
}
}
}
}
}
