时间复杂度为O(N)的排序算法主要有三种——桶排序、计数排序与基数排序，后两者是基于桶排序的思想
1.桶排序
·基本思想
给定一个数组arr，数组内都是整数，整数都是处于0到9之间的。于是可以定义一个大小为10的数组b(这个大小通过极值差+1可以尽量的减少大小)，初始值为0，表示10个桶。遍历待排序数组arr，将arr对应的值放在b中对应的位置(即b[arr[i]]++)，arr中的3使b[3]+1,如果arr中有两个3则b[3]的值成为2；
然后遍历b这个数组，即是遍历桶，将桶中数据“倒”出来，如果b[i]的值为2，则输出两次，如此就完成了整个桶排序。
·代码实现
public void bucketSort(int [] arr) {
int max = arr[0],min = arr[0];
//找到元素的极值差+1作为计数数组大小
for(int i:arr){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}
int n=max-min+1;
int[] b = new int[n];
for(int i = 0 ; i < arr.length ; i ++) {
//装入桶
b[arr[i]]++;
}
for(int i = 0 ; i < b.length ; i ++) {
//b[i]是多大，则输出几次
while(b[i]!=0) {
//按次数顺序输出
System.out.println(i);
b[i]--;
}
}
}
·性能分析
桶排序号称最快最简单的算法，排序过程中只进行了一次遍历，因此时间复杂度就是O(N)，但是在排序的过程中申请了一个额外的数组(假设大小是M)，额外空进复杂度就是O(M)，偶尔也使用链表来完成重复数据的存储，而不采取计数的方式，一般来说，认为桶排序是稳定的。2.计数排序
·基本思想
先明确一个概念：一个有序序列中，元素k的秩，等于这个序列中，小于等于元素k的的元素个数。
计数排序基于桶排序的思想，假设待排序数组arr，先找出取值的范围(即已经限定的范围或者序列中max-min+1)，依据这个范围定义桶的大小，装入桶的过程与桶排序相同，都是对序列中的元素进行计数；然后每个桶的计数=前一个桶的计数+自身桶的计数，这样下来，每一个桶的计数就等于桶中元素的秩，于是可以有，桶中元素的大小b[arr[i]]即表示arr[i]排序之后所在位置的下标。这样同时也可以处理相同元素的问题，因为所有的相同元素与不同元素都进行了计数，只需要输出排序后的数组，就可以保持原序列的元素不变。
代码实现
public int[] countSort(int[] arr) {
int max = arr[0],min = arr[0];
//找到元素的极值差+1作为计数数组大小
for(int i:arr){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}
int n=max-min+1;
int[] b = new int[n];
for(int i = 0 ; i < arr.length ; i ++) {
//arr[i]对应的元素所在下标计数+1
b[arr[i]-min]++;
}
for(int i = 1 ; i < b.length ; i ++) {
//记录不大于当前元素的个数
b[i] = b[i] + b[i-1];
}
int [] c = new int[arr.length];
for(int i = arr.length-1 ; i >= 0 ; i --) {
//计数数组-1就是当前元素对应的秩，用原数组的当前值赋值
//b[arr[i]-min]表示arr[i]这个元素的秩，-1则可以表示所在的下标
c[--b[arr[i]-min]]=arr[i];
}
return c;
}
性能分析
如果计数数组范围本身就很小，只需要进行三次遍历就可以排序完毕；如果想减少计数数组的大小，则还需要一次遍历来找到极值差+1；计数排序不是基于比较的方式来排序的，辅助数组的大小为M的话，时间复杂度则为O(M+N)，额外空间复杂度就是O(M+N)，有一种理想的状态，就是M<<N的时候，此时，数据多而不散，集中在一个小范围内，此时，时间复杂度就是O(N)。同理，计数排序也是稳定的排序算法。
3.基数排序
·基本思想
假设待排序数组arr，我们可以知道数组的最大数的位数maxDigit，准备一个大小为10的数组buckets，表示0~9位，接下来，在循环maxDigit次中，分别把所有的数字按照
·代码实现
/**
*
* @param arr 待排序数组
* @param index 以10为初值，每次乘以10
* @param maxDigit 最长的数字的位数
*/
public void radixSort(int[] arr,int index,int maxDigit) {
//使用temp数组存储arr数组的所有值
int[] temp = new int[arr.length];
//定义10个桶
int[] buckets = new int [index];
//用于计算当前位数的值
int rate = 1;
for(int i = 0; i < maxDigit ; i ++) {
//每次排序需要重置桶
Arrays.fill(buckets, 0);
//将arr复制到temp
System.arraycopy(arr, 0, temp, 0, arr.length);
for(int j = 0 ; j < arr.length ; j ++) {
buckets[(temp[j]/rate)%index]++;
}
//计数
for(int j = 1 ; j < index ; j ++) {
buckets[j] = buckets[j] + buckets[j-1];
}
for(int j = arr.length-1 ; j >= 0 ; j --) {
arr[--buckets[(temp[j]/rate)%index]] = temp[j];
}
rate *= index;
}
}
性能分析
基数排序不是基于比较的方式来排序的，基数排序的时间复杂度一般认为是O(N)，额外空间复杂度还需要定义一个辅助数组，辅助数组的大小为M的话，额外空间复杂度是O(M+N)。基数排序也是稳定的排序算法。