把这三个拿到一起来说，是因为这三种排序思想很像。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。（这里再说一下其他排序）
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
1.计数排序：
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。
计数排序的基本思想是：对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。
过程：
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1输出数组 int[] res = new int[arr.length];1.求出待排序数组的最大值max=6， 最小值min=1
2.实例化辅助计数数组help，help数组中每个下标对应arr中的一个元素，help用来记录每个元素出现的次数3.计算 arr 中每个元素在help中的位置 position = arr[i] - min，此时 help = [1,0,2,1,1,1]; （3出现了两次，2未出现）4.根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]1 public static int[] countSort1(int[] arr){ 2 if (arr == null || arr.length == 0) { 3 return null; 4 } 5 6 int max = Integer.MIN_VALUE; 7 int min = Integer.MAX_VALUE; 8 9 //找出数组中的最大最小值10 for(int i = 0; i < arr.length; i++){11 max = Math.max(max, arr[i]);12 min = Math.min(min, arr[i]);13 }14 15 int help[] = new int[max];16 17 //找出每个数字出现的次数18 for(int i = 0; i < arr.length; i++){19 int mapPos = arr[i] - min;20 help[mapPos]++;21 }22 23 int index = 0;24 for(int i = 0; i < help.length; i++){25 while(help[i]-- > 0){26 arr[index++] = i+min;27 }28 }29 30 return arr;31 } 另一种实现：
需要三个数组:
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1输出数组 int[] res = new int[arr.length];1.求出待排序数组的最大值max=6， 最小值min=1
2.实例化辅助计数数组help，help用来记录每个元素之前出现的元素个数3.计算 arr 每个数字应该在排序后数组中应该处于的位置，此时 help = [1,1,3,4,5,6];4.根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]1 public static int[] countSort2(int[] arr){ 2 int max = Integer.MIN_VALUE; 3 int min = Integer.MAX_VALUE; 4 5 //找出数组中的最大最小值 6 for(int i = 0; i < arr.length; i++){ 7 max = Math.max(max, arr[i]); 8 min = Math.min(min, arr[i]); 9 }10 11 int[] help = new int[max - min + 1];12 13 //找出每个数字出现的次数14 for(int i = 0; i < arr.length; i++){15 int mapPos = arr[i] - min;16 help[mapPos]++;17 }18 19 //计算每个数字应该在排序后数组中应该处于的位置20 for(int i = 1; i < help.length; i++){21 help[i] = help[i-1] + help[i];22 }23 24 //根据help数组进行排序25 int res[] = new int[arr.length];26 for(int i = 0; i < arr.length; i++){27 int post = --help[arr[i] - min];28 res[post] = arr[i];29 }30 31 return res;32 }
2.桶排序
桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
1.找出待排序数组中的最大值max、最小值min
2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+13.遍历数组 arr，计算每个元素 arr[i] 放的桶4.每个桶各自排序5.遍历桶数组，把排序好的元素放进输出数组1 public static void bucketSort(int[] arr){ 2 3 int max = Integer.MIN_VALUE; 4 int min = Integer.MAX_VALUE; 5 for(int i = 0; i < arr.length; i++){ 6 max = Math.max(max, arr[i]); 7 min = Math.min(min, arr[i]); 8 } 9 10 //桶数11 int bucketNum = (max - min) / arr.length + 1;12 ArrayList > bucketArr = new ArrayList<>(bucketNum);13 for(int i = 0; i < bucketNum; i++){14 bucketArr.add(new ArrayList ());15 }16 17 //将每个元素放入桶18 for(int i = 0; i < arr.length; i++){19 int num = (arr[i] - min) / (arr.length);20 bucketArr.get(num).add(arr[i]);21 }22 23 //对每个桶进行排序24 for(int i = 0; i < bucketArr.size(); i++){25 Collections.sort(bucketArr.get(i));26 }27 28 System.out.println(bucketArr.toString());29 30 }
3.基数排序
基数排序已经不再是一种常规的排序方式，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。人得习惯思维是最高位优先方式。但一旦这样，当开始比较十位时，程序还需要判断它们的百位是否相同--这就认为地增加了难度，计算机通常会选择最低位优先法。
基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。
1 import java.util.Arrays; 2 3 public class MultiKeyRadixSortTest { 4 5 public static void main(String[] args) { 6 int[] data = new int[] { 1100, 192, 221, 12, 23 }; 7 print(data); 8 radixSort(data, 10, 4); 9 System.out.println("排序后的数组：");10 print(data);11 }12 13 public static void radixSort(int[] data, int radix, int d) {14 // 缓存数组15 int[] tmp = new int[data.length];16 // buckets用于记录待排序元素的信息17 // buckets数组定义了max-min个桶18 int[] buckets = new int[radix];19 20 for (int i = 0, rate = 1; i < d; i++) {21 22 // 重置count数组，开始统计下一个关键字23 Arrays.fill(buckets, 0);24 // 将data中的元素完全复制到tmp数组中25 System.arraycopy(data, 0, tmp, 0, data.length);26 27 // 计算每个待排序数据的子关键字28 for (int j = 0; j < data.length; j++) {29 int subKey = (tmp[j] / rate) % radix;30 buckets[subKey]++;31 }32 33 for (int j = 1; j < radix; j++) {34 buckets[j] = buckets[j] + buckets[j - 1];35 }36 37 // 按子关键字对指定的数据进行排序38 for (int m = data.length - 1; m >= 0; m--) {39 int subKey = (tmp[m] / rate) % radix;40 data[--buckets[subKey]] = tmp[m];41 }42 rate *= radix;43 }44 45 }46 47 public static void print(int[] data) {48 for (int i = 0; i < data.length; i++) {49 System.out.print(data[i] + "\t");50 }51 System.out.println();52 }53 54 }