上次把时间复杂度趋近于O（nlogn）的算法写完了，这次先接着把时间复杂度O（n）的两个算法写完。它们分别是计数排序和基数排序，由于O（nlogn）已经是基于比较的排序算法的下限，这两个算法都不需要比较。
一、计数排序
时间复杂度O（n），空间复杂度O（k），k是输入序列的值的范围（最大值-最小值），是稳定的。计数排序一般用于已知输入值的范围相对较小，比如给公司员工的身高体重信息排序。
算法导论里面讲的计数排序大致是这样的思路：
假设n个输入元素中的每一个都是介于0到k之间的整数，对每一个输入元素x，确定出小于x的元素个数，有了这一信息，就可以把x直接放在它在最终输出数组的位置上，例如，如果有17个元素小于x，则x就是属于第18个输出位置。当几个元素相同是，方案要略作修改。
我感觉这种方法不太好理解，而且代码写起来也麻烦。所以我下面的代码是用桶排序的思想实现的。
这种实现有点像散列里的键值转换思想，把输入的值映射成桶的序号（桶数组的下标），然后再遍历一遍桶数组把元素倒出。过程大致是根据输入序列的值的范围k，创建k个桶（用大小为k的数组表示，下标表示桶的序号，值表示该桶里元素个数）。遍历一遍输入数组，放入相应位置的桶里，再把桶按顺序倒出来即可。
举个例子，假设输入数组A为{3，5，1，2，4，3}，值的范围是1~5，所以创建5个桶，序号1，2，3，4，5。装桶时遍历一遍输入数组，A[0]=3，把它放到3号桶；A[1]=5，放到5号桶；1放到1号桶……最后3放到3号桶。现在三号桶的值为2，其他桶的值为1，再遍历一遍桶数组，按顺序把桶倒出，元素被倒出的顺序就是排序的顺序了。
import java.util.*;
public class CountingSort {
public int[] countingSort(int[] A, int n) {
//找数组中的最大值和最小值，确定桶的个数
int max=A[0];
int min=A[0];
for(int i=0;i<n;i++){
if(A[i]>max)
max=A[i];
if(A[i]<min)
min=A[i];
}
//定义桶数组B并初始化
int[] B= new int[max-min+1];
for(int i=0;i<max-min+1;i++)
B[i]=0;
//把数组A的元素装到对应桶里
for(int i=0;i<n;i++){
B[A[i]-min]++;
}
//把所有桶倒出来
for(int i=0,j=0;j<max-min+1;j++){
//倒桶j
for(int k=B[j];k>0;k--){
A[i++]=j+min;
}
}
return A;
}
}
二、基数排序
1.多关键字排序思想
基数排序时一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。按照关键字先后顺序，基数排序可以分为高位优先法和低位优先法。
比如说，对扑克牌排序，规定花色（假设黑桃>梅花>红桃>方片）优先级高于面值，花色是主关键字，面值是次关键字。我们可以先按照花色将扑克牌分为有序的四堆，再对每一堆分别按照面值排序。这就是所谓的高位优先法。是不是感觉和归并有点像？这是因为这里也是利用了分治法思想进行的排序。
低位优先法则与上面相反。先按面值把扑克牌分成13堆（叫分配操作），再按顺序把这13堆从小到大叠起来（收集），然后再对花色执行分配收集操作，然后扑克就成有序的了。
再看值是数字的例子。假设输入为{234，112，73，252，31}，我们可以把个位，十位，百位上的数字看作四个关键字，优先级依次升高。按上面的思想，先按百位分成三堆{73，31；112；234，252}（0；1；2），在每一堆内再分别按十位分，{31，73；112；234，252}，再按个位分。这就是高位优先，低位优先和上面也是一样的道理。
一般来说低位优先法要比高位简单。因为高位优先是分治法思想，对子集按相同方法排序，是一个递归的过程。而低位优先法只要通过x次分配收集操作就可以完成排序，x是取决于关键字的多少。
2.桶排序思想实现基数排序
书上讲的基数排序算法就是利用桶的思想实现低位优先法，按照输入数值的各个位作为关键字进行排序。时间复杂度O（xn）=O（n），因为每次分配收集操作都是线性时间，关键词个数x也是常量。空间复杂度也大大减小，为O（1），桶的个数也是常量。是个稳定的排序算法。但是由于基数排序非常不灵活，输入数据类型稍有变化，可能就要重写，重新规定关键字等问题。所以基数排序并没有其他算法使用广泛。
下面讲算法的实现。也是利用桶排序思想。假设输入数据都是十进制的，都是四位数以内的数。我们准备十个桶，序号0，1，2，3，4，5，6，7，8，9。我们首先根据个位上的数值选择进入哪一个桶，然后按顺序倒出，进行第一次排序。然后再根据十位上的数进入桶，再倒出。然后百位，千位，进行四次分配收集。
计数排序算法里的桶只需要存储元素的个数，所以一个int值即可。但现在桶里面要存储元素的数值，所以每个桶就要用别的方式表示了。我在下面的代码中写的是
int [][] B = new int [10][n];
就是创建了十个桶，每个桶是大小为n的数组，因为每个桶里最多可能要放n个元素。但是这样写空间开销很大，大量空间都被浪费了。更好的做法应该是用链表来存储桶里的元素（但是我是写完才意识到的，就懒得改了。。。）。而且桶应该是用一个队列表示的。其实如果是在线做题的话，完全可以用一个Queue类表示，很简单。
我之前在做在线题的时候有一次需要用到堆，然后我自己就写了一个堆，花时间不说，还出错了。。。但其实完全可以用优先队列类辅助。面试的话面试官可能想考察你堆的掌握，但在线题只要OC就行了嘛。毕竟我们用的是java。反思自己还是对java不够熟悉，做算法题还是停留在c/c++的思维里，并没有利用java的特性。下面上代码，因为写的时候思路不清晰，而且没用链表队列表示桶，所以可能有点乱，大家凑乎看。
package fuckingtest;
import java.util.*;
public class RadixSort {
public int[] radixSort(int[] A, int n) {
//定义桶数组B并初始化,每个桶的第一个元素表示桶内元素个数
int[][] B= new int[10][n+1];
for(int i=0;i<10;i++)
for(int j=0;j<n+1;j++)
B[i][j]=0;
for(int x=1;x<=4;x++){
//把数组A的第x位元素装到对应桶里
for(int i=0;i<n;i++){
B[getNum(A[i],x)][0]++;
B[getNum(A[i],x)][B[getNum(A[i],x)][0]]=A[i];
}
//把所有桶倒出来
for(int i=0,j=0;j<10;j++){
//倒桶j
for(int k=1;B[j][0]>0&&k<=B[j][0];k++){
A[i++]=B[j][k];
}
B[j][0]=0;
}
}
return A;
}
int getNum(int x,int d){
int[] a={1,1,10,100,1000};
System.out.println((x/a[d])%10);
return (x/a[d])%10;
}
public static void main(String[] args) {
int[] r=new int[6];
int[] a=new int[]{109,551,32,4,294,6};
RadixSort h = new RadixSort();
r = h.radixSort(a,6);
for(int t:r){
System.out.println(t);
}
}
}
