//桶式排序
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]--;
               }
          }
     }
}

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++;
          }
     }
}

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++;
          }
     }
}