基数排序，又称为桶排序的拓展
1，接下来看图理解实现的过程
定义10个桶，相当于定义了一个二维数组，每个桶相当于一个以为数组
以数组中的每个数据的各个位数上的值进行比较，即先各位，再1十位，再百位…一直下去
以int data[] = {53,3,542,748,14,214}为例
对以个数的大小进行划分，顺序的存入到不同的桶中
第一轮，先判断各位上的数，得到的的数据为{542，53,3，14,214,748}
在将桶中的数据放回给原数组中，并将桶中的数据置空
第二轮，对十位进行排序，如果位数不够，则在前面补0
得到的的数据为{3, 14, 214, 542, 748, 53}
第三轮，对百位进行排序，桶中的数据置空，得到的数据为{3, 14, 53, 214, 542, 748}
这样就可以发现顺序已经拍好了
2，代码实现
原生代码实现
package sanguigu.sort; import java.util.Arrays; /** * 基数排序 * 桶排序的应用 * @author zhenghuisheng */ public class Jishu { public static void main(String[] args) { int dd[] = {53,3,542,748,14,214}; jishu(dd); } public static void jishu(int a[]){ //定义一个二维数组，用于存储数据，相当于定义了10个桶，每个桶代表一个一维数组 //10表示0到9，而a.length表示我们做最坏的打算，可能将所有的数据都存在1个桶中 int data[][] = new int[10][a.length]; //定义一个数组，用于保存数据的个数，整型数组的每个数据默认为0 int digitElement[] = new int[10]; //需要遍历的次数取决去数组中最大数据的位数，位数小的数据前面补0 //第一次遍历，即个数遍历 //开始遍历数组中的每个数据 for (int i = 0; i < a.length; i++) { //取余 int k = a[i] % 10; //digitElement[i],代表10个桶中的数据的个数,说白了就是一个计数器，但是可以记录下标，方便使用 data[k][digitElement[k]] = a[i]; //经典桶排序 digitElement[k] ++ ; } //在存放在桶的数据中，将数据放回原来的数组中，即数组a中 int index = 0; for (int i = 0; i < digitElement.length; i++) { if(digitElement[i] != 0){ //遍历桶中的个数，将桶中的数据去除 for (int j = 0; j < digitElement[i]; j++) { a[index] = data[i][j]; index ++; } } //将存数据个数的桶中的数据置空 digitElement[i] = 0; } System.out.println(Arrays.toString(a)); System.out.println("=========================第一次遍历==========================="); for (int i = 0; i < a.length; i++) { //取余 int k = a[i]/10 % 10; //digitElement[i],代表10个桶中的数据的个数,说白了就是一个计数器，但是可以记录下标，方便使用 data[k][digitElement[k]] = a[i]; //经典桶排序 digitElement[k] ++ ; } //在存放在桶的数据中，将数据放回原来的数组中，即数组a中 int index1 = 0; for (int i = 0; i < digitElement.length; i++) { if(digitElement[i] != 0){ //遍历桶中的个数，将桶中的数据去除 for (int j = 0; j < digitElement[i]; j++) { a[index1] = data[i][j]; index1 ++; } } //将存数据个数的桶中的数据置空 digitElement[i] = 0; } System.out.println(Arrays.toString(a)); System.out.println("=========================第二次遍历==========================="); for (int i = 0; i < a.length; i++) { //取余 int k = a[i]/100; //digitElement[i],代表10个桶中的数据的个数,说白了就是一个计数器，但是可以记录下标，方便使用 data[k][digitElement[k]] = a[i]; //经典桶排序 digitElement[k] ++ ; } //在存放在桶的数据中，将数据放回原来的数组中，即数组a中 int index2 = 0; for (int i = 0; i < digitElement.length; i++) { if(digitElement[i] != 0){ //遍历桶中的个数，将桶中的数据去除 for (int j = 0; j < digitElement[i]; j++) { a[index2] = data[i][j]; index2 ++; } } //将存数据个数的桶中的数据置空 digitElement[i] = 0; } System.out.println(Arrays.toString(a)); System.out.println("=========================第三次遍历==========================="); } }
优化后
package sanguigu.sort; import java.util.Arrays; /** * 基数排序 * 桶排序的应用 * @author zhenghuisheng */ public class Jishu { public static void main(String[] args) { int dd[] = {53,3,542,748,14,214}; jishu(dd); } public static void jishu(int a[]){ //定义一个二维数组，用于存储数据，相当于定义了10个桶，每个桶代表一个一维数组 //10表示0到9，而a.length表示我们做最坏的打算，可能将所有的数据都存在1个桶中 int data[][] = new int[10][a.length]; //定义一个数组，用于保存数据的个数，整型数组的每个数据默认为0 int digitElement[] = new int[10]; //需要遍历的次数取决去数组中最大数据的位数，位数小的数据前面补0 int max = a[1]; for (int i = 0; i < a.length; i++) { if(max < a[i]){ max = a[i]; } } //获取最大值，通过最大值来确定需要遍历的次数 System.out.println(max); int num = (max + "").length(); for (int j = 0; j <num ; j++) { for (int i = 0; i < a.length; i++) { //取余 int k = a[i] /(int)Math.pow(10,j) % 10; //digitElement[i],代表10个桶中的数据的个数,说白了就是一个计数器，但是可以记录下标，方便使用 data[k][digitElement[k]] = a[i]; //经典桶排序 digitElement[k] ++ ; } //在存放在桶的数据中，将数据放回原来的数组中，即数组a中 int index = 0; for (int i = 0; i < digitElement.length; i++) { if(digitElement[i] != 0){ //遍历桶中的个数，将桶中的数据去除 for (int k = 0; k < digitElement[i]; k++) { a[index] = data[i][k]; index ++; } } //将存数据个数的桶中的数据置空 digitElement[i] = 0; } System.out.println(Arrays.toString(a)); System.out.println("=========================第" +j+1+"次遍历==========================="); }
3,时间复复杂度为：
时间复杂度为O(d*n) 。其中，n是数组长度，d是最大位数
4,注意的问题
由于该算法是以空间换时间，从而提高算法的效率，因此需要注意数据的大小，如果数据过大，很容易造成堆溢出
