桶式排序与基数排序举例及 JAVA 代码实现
桶式排序
概念
有限个数字 m，每个数字的大小都在 1 与 n 之间，则我们可以假设有 n 个桶，遍历 m 个数字，将其存入对应的桶中（如数字的值为 3，就存入 3 号桶，桶的值对应存入数字的个数）
例子
有数字 3,3,5,1,2，大小均在 0-5 之间，所以我们假设有 5 个桶，分别标号 1,2,3,4,5，遍历所有数字，将其存入桶中，则存储之后，所有桶的计数如下：
| 桶号 | 1 | 2 | 3 | 4 | 5 |
| 计数 | 1 | 1 | 2 | 0 | 1 |
我们按照桶的序号将数字倒出来，如下：
| 桶的倒出顺序 | 数字队列 |
| 5号桶倒出1个5 | 5 |
| 4号桶倒出0个4 | 5 |
| 3号桶倒出2个3 | 5,3,3 |
| 2号桶倒出1个2 | 5,3,3,2 |
| 1号桶倒出1个1 | 5,3,3,2,1 |
如上所示，我们成功将所给数列按照从大到小的排序，反之，如果从 1 号桶开始倒出，我们会得到从小到大排列的数字
代码实现（JAVA）
//桶式排序
public class BucketSort{
public static void main(String[] args){
int[] a = {2,4,15,11,6,3,7,19,8,5,4};
sort(a,19);
}
//桶式排序函数
//a是要排序的数组
//max是最大数字（这里我们默认数字最小为0）
public static void sort(int[] a,int max){
//声明一个数组，这就是桶，编号从0到max的桶，一共max+1个
int[] count = new int[max + 1];
//遍历数组，用桶计数
for(int i = 0;i < a.length;i++){
count[a[i]]++;
}
//将桶里面的数字倒出
for(int i = max;i > 0;i--){
while(count[i] > 0){
System.out.print(i + " ");
count[i]--;
}
}
}
}弊端
如果我们的数字波动范围非常大，比如 1 到 10000，那么我们需要一个 10000 元素数组的空间开销，而且在倒出数字的时候需要遍历 10000 个桶，这样效率是非常低的，于是我们有了基于桶式排序的基数排序
***
基数排序
概念
基于桶式排序，将要排序的数字一位一位的比较，经历多次桶式排序，得出最终的序列
如果要排序的元素可以分成多位，并且每一位都在一个固定的范围内，则可以用这种排序方法，如对 10 进制数字的排序
例子
有数字 23,35,9,73,3,314,11,1234,5，可以看出来，每一位数字的取值范围都是 0 到 9，所以我们可以用 10 个桶来进行排序，分别编号 0 到 9。
- 第一遍排序，按照最低位数字将各个数字存入桶中：
| 桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 存放数字 | 11 | 23,73,3 | 3,141,234 | 35,5 | 9 |
按照桶的序号将所有的数字倒出来，对于一个桶内有多个数字的情况，我们按照先进先出的原则倒出数字：
| 桶的倒出顺序 | 数字队列 |
| 9 | 9 |
| 8 | 9 |
| 7 | 9 |
| 6 | 9 |
| 5 | 9,35,5 |
| 4 | 9,35,5,314,1234 |
| 3 | 9,35,5,314,1234,23,73,3 |
| 2 | 9,35,5,314,1234,23,73,3 |
| 1 | 9,35,5,314,1234,23,73,3,11 |
| 0 | 9,35,5,314,1234,23,73,3,11 |
我们可以看到第一遍排序好的数字还是很乱的，可能还不能基数排序的妙处，不急，下面我们进行第二次排序
- 第二遍排序，将第一次排好的序列 9,35,5,314,1234,23,73,3,11，按照第二位的数字存入桶中（只有一位的数第二位为 0）：
| 桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 存放数字 | 9,5,3 | 314,11 | 23 | 35,1234 | 73 |
按照桶的序号将所有的数字倒出来，对于一个桶内有多个数字的情况，我们按照先进先出的原则倒出数字：
| 桶的倒出顺序 | 数字队列 |
| 9 | |
| 8 | |
| 7 | 73 |
| 6 | 73 |
| 5 | 73 |
| 4 | 73 |
| 3 | 73,35,1234 |
| 2 | 73,35,1234,23 |
| 1 | 73,35,1234,23,314,11 |
| 0 | 73,35,1234,23,314,11,9,5,3 |
我们发现，第二遍之后，有些数字好像已经排序好了，经过两次排序，或许你已经能看出来一些基数排序的原理了，下面我们进行第三遍排序
- 第三遍排序，将第二次排好的序列 73,35,1234,23,314,11,9,5,3，按照第三位的数字存入桶中（只有两位的数第三位为 0）：
| 桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 存放数字 | 73,35,23,11,9,5,3 | 1234 | 314 |
按照桶的序号将所有的数字倒出来，对于一个桶内有多个数字的情况，我们按照先进先出的原则倒出数字：
| 桶的倒出顺序 | 数字队列 |
| 9 | |
| 8 | |
| 7 | |
| 6 | |
| 5 | |
| 4 | |
| 3 | 314 |
| 2 | 314,1234 |
| 1 | 314,1234 |
| 0 | 314,1234,73,35,23,11,9,5,3 |
第三遍排序结束，相信你已经看出来基数排序的原理了，如果你还不懂，后面会有一个 flash，清晰明了的一步一步为你分解基数排序，在这之前，让我们先勤勤恳恳的把第四遍，也是最后一遍排序完成
- 第四遍排序，将第三次排好的序列 314,1234,73,35,23,11,9,5,3，按照第四位的数字存入桶中（只有三位的数第四位为 0）：
| 桶号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 存放数字 | 314,73,35,23,11,9,5,3 | 1234 |
按照桶的序号将所有的数字倒出来，对于一个桶内有多个数字的情况，我们按照先进先出的原则倒出数字：
| 桶的倒出顺序 | 数字队列 |
| 9 | |
| 8 | |
| 7 | |
| 6 | |
| 5 | |
| 4 | |
| 3 | |
| 2 | |
| 1 | 1234 |
| 0 | 1234,314,73,35,23,11,9,5,3 |
至此，我们终于完成了排序，如果你还是不能理解，请戳下面的链接，里面的 flash 比文字简单直接好理解的多
代码实现（JAVA）
正常情况下，我们是要告诉我们的排序方法，我们最高位的数字是几位的，这样在最高位也排序完成后就会停止排序，但是我们在这段代码中用了一个叫 hasNum 的 boolean 型变量，用来表征我们的数组中是否还存在更高的位数，具体实现参见下面的代码，有注释，不难理解（PS：虽然省事了，方法更通用了，但是也产生了额外的开销）
public class RadixSort{
public static void main(String[] args){
//声明要排序的数组
int[] data = {73,22,93,867494,43,55,123,8978,10000,14,28,65,39,81,33,100,567};
//调用基数排序函数
sort(data,10);
//输出排序后的数组
for(int i = 0;i < data.length;i++){
System.out.print(data[i] + " ");
}
}
///基数排序函数
//a表示要排序的数组
//d表示每一位数字的范围（这里是10进制数，有0~9一共10种情况）
public static void sort(int[] a,int d){
//n用来表示当前排序的是第几位
int n = 1;
//hasNum用来表示数组中是否有至少一个数字存在第n位
boolean hasNum = false;
//二维数组temp用来保存当前排序的数字
//第一维d表示一共有d个桶
//第二维a.length表示每个桶最多可能存放a.length个数字
int[][] temp = new int[d][a.length];
int[] order = new int[d];
while(true){
//判断是否所有元素均无比更高位，因为第一遍一定要先排序一次，所以有n!=1的判断
if(n != 1 && !hasNum){
break;
}
hasNum = false;
//遍历要排序的数组，将其存入temp数组中（按照第n位上的数字将数字放入桶中）
for(int i = 0;i < a.length;i++){
int x = a[i]/(n*10);
if(x != 0){
hasNum = true;
}
int lsd = (x%10);
temp[lsd][order[lsd]] = a[i];
order[lsd]++;
}
//k用来将排序好的temp数组存入data数组（将桶中的数字倒出）
int k = 0;
for(int i = 0;i < d;i++){
if(order[i] != 0){
for(int j = 0;j < order[i];j++){
a[k] = temp[i][j];
k++;
}
}
order[i] = 0;
}
n++;
}
}
}***
基数排序（给英文字符串排序）
排序规则
- 字符串更长的在前
- z 在最前，a 在最后
代码实现（JAVA）
总感觉代码写的比较笨，但是智商确实有点不够用了…………..
public class RadixSort_Letter{
public static void main(String[] args){
//声明要排序的数组
String[] a = {"ac","ee","ef","b","z","f","ep","gaaa","azh","az","r"};
//调用基数排序函数
sort(a,4);
//输出排序后的数组
for(int i = a.length - 1;i >= 0;i--){
System.out.print(a[i] + " ");
}
}
///基数排序函数
//a是要排序的数组
//m表示数组元素最高位数，如我们排序的数组中位数最高的元素为gaaa，有4位
public static void sort(String[] a,int m){
int n = 0;
//27表示每一位字符分成27类，其中1~26对应'a'~'z'
//第0位专门用来存放没有高位字符的数组元素，如在比较第二位字符时，b,z,f等没有第二位字符的元素就存在temp[0]中
//相对应的，ac存在temp[1]中，ef存在temp[5]中
String[][] temp = new String[27][a.length];
int[] order = new int[27];
while(n < m){
//这里声明String类型的数组b，将数组a中的每个元素倒序，然后放入数组b
//如a[0]="abc"，则b[0]="cba"
//之所以这样做，是为了解决下面调用charAt方法时索引的问题，脑子太笨，没想到更好的方法
String[] b = new String[a.length];
for(int i = 0;i < a.length;i++){
if(a[i].length() > 1){
StringBuffer sb = new StringBuffer(a[i]);
sb.reverse();
b[i] = new String(sb);
}else{
b[i] = a[i];
}
}
for(int i = 0;i < a.length;i++){
if(a[i].length() > n){
int lsd = b[i].charAt(n) - 'a' + 1;
temp[lsd][order[lsd]] = a[i];
order[lsd]++;
}else{
temp[0][order[0]] = a[i];
order[0]++;
}
}
int k = 0;
for(int i = 0;i < 27;i++){
for(int j = 0;j < order[i];j++){
a[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n++;
}
}
}