一、桶排序（Bucket sort）：
1、原理：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
2、桶排序原理示意图：
3、实现代码：
public static void BucketSort(int[] arr){
//最大最小值
int max = arr[0];
int min = arr[0];
int length = arr.length;
for(int i=1; i<length; i++) {
if(arr[i] > max) {
max = arr[i];
} else if(arr[i] < min) {
min = arr[i];
}
}
//最大值和最小值的差
int diff = max - min;
//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < length; i++){
bucketList.add(new ArrayList<>());
}
//每个桶的存数区间
float section = (float) diff / (float) (length - 1);
//数据入桶
for(int i = 0; i < length; i++){
//当前数除以区间得出存放桶的位置 减1后得出桶的下标
int num = (int) (arr[i] / section) - 1;
if(num < 0){
num = 0;
}
bucketList.get(num).add(arr[i]);
}
//桶内排序
for(int i = 0; i < bucketList.size(); i++){
//可以使用快排
Collections.sort(bucketList.get(i));
}
//写入原数组
int index = 0;
for(ArrayList<Integer> arrayList : bucketList){
for(int value : arrayList){
arr[index] = value;
index++;
}
}
}
4、桶排序的时间复杂度是多少？
如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk)。 m个桶排序的时间复杂度就是O(m * k * logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n*log(n/m))。当桶的个数m接近数据个数n时， log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。
二、计数排序（Counting sort）：
1、原理：当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序要求输入的数据必须是有确定范围的整数。
2、计数排序原理示意图：
3、实现代码：
// 计数排序， a是数组， n是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] arr){
//找出数组中的最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//初始化计数数组
int[] countArr = new int[max + 1];
//计数
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
arr[i] = 0;
}
//排序
int index = 0;
for (int i = 0; i < countArr.length; i++) {
if (countArr[i] > 0) {
arr[index++] = i;
}
}
}
三、基数排序（Radix sort）：
1、原理：将数据按位数切割成不同的数字，然后按每个位数分别比较。从后往前比较。
2、注意：
a、这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
b、对于要排序的数据并不是等长的，可以根据ASCII值，来补齐，一般都补“0”，因为无论是字母还是数字，它们的ASCII值都大于等于“0”的ASCII值。
c、基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。
3、基数排序原理示意图：
4、实现代码：
public static void RadixSort(int[] arr){
int length = arr.length;
//最大值
int max = arr[0];
for(int i = 0;i < length;i++){
if(arr[i] > max){
max = arr[i];
}
}
//当前排序位置
int location = 1;
//桶列表
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
//长度为10 装入余数0-9的数据
for(int i = 0; i < 10; i++){
bucketList.add(new ArrayList());
}
while(true)
{
//判断是否排完
int dd = (int)Math.pow(10，(location - 1));
if(max < dd){
break;
}
//数据入桶
for(int i = 0; i < length; i++)
{
//计算余数 放入相应的桶
int number = ((arr[i] / dd) % 10);
bucketList.get(number).add(arr[i]);
}
//写回数组
int nn = 0;
for (int i=0;i<10;i++){
int size = bucketList.get(i).size();
for(int ii = 0;ii < size;ii ++){
arr[nn++] = bucketList.get(i).get(ii);
}
bucketList.get(i).clear();
}
location++;
}
}
