任何只使用比较的一般排序算法在最坏情况下需要时间，但是在某些特殊情况下（对于待排序元素有提供额外的信息）以线性时间进行排序是可能的。
桶排序
适用的情形举例
为了使桶排序能够正常工作，必须有一些附加的信息。我们考虑下面这种情况：
输入数据都是小于M的正整数，对这些数字进行排序。
解决的算法
使用一个大小为M的称为count的数组，初始化为全0。于是，count有M个单元（或者称为桶），初始为空。当读入时，
增1。在所有的输入数据被读入后，扫描数组count，如果
大于0，那么连续打印
，次数为
。即可将所有的元素有序地打印出来。如果M为O(N)，那么总时间就是O(N)。
缺点
如果M很大，那么会有太多的桶，浪费空间。可以用基数排序解决这个问题。
基数排序
适用情形举例
假设我们有值域从0~999的10个数字要排序，为了避免使用大量的桶，我们分几趟桶排序来解决这个问题。一种简单并正确的思路是先对最低位数字进行桶排序，然后是次低位，以此类推。当然，可能有多个数落入同一个桶里，与上面介绍的原始桶排序情形不同的是，这些数可以是不同的，所以我们得把它们存在一个表里（而不是计数）。每一趟排序都是稳定的：当前位数字相同的这些元素仍然保留前几趟所确定的顺序。下面我们举例说明对64, 8, 216, 512, 27, 729, 0, 1, 343, 125进行排序的结果，我们通过补0来使十位和百位数字更加清晰。在第一趟之后，元素按照最低位有序。一般地，在第k趟之后，元素按照第k低位有序。所以最终元素就完全有序了。
注意：当几个数进入同一个桶中时，保证有序地入桶，并且有序地出桶。即对于进入同一个桶的元素，先进入的元素在出桶时也要保证先出。
基数排序的应用之一是等长字符串排序：
public static void radixSortA(String[] arr, int strLen) {
final int BUCKETS = 256;
ArrayList<String>[] buckets = new ArrayList[BUCKETS];
for (int i = 0; i < BUCKETS; i++) {
buckets[i] = new ArrayList<String>();
}
// 从最低位开始
for (int pos = strLen - 1; pos >= 0; pos--) {
for (String s : arr) {
buckets[s.charAt(pos)].add(s);
}
int index = 0;
for (ArrayList<String> bucket : buckets) {
for (String s : bucket) {
arr[index++] = s;
}
// 桶要清空, 因为每一趟重新排序, 桶必须是空的
bucket.clear();
}
}
}
对于变长字符串排序，可以由上述算法稍加扩展解决。举例如下：
首先将字符串按照其长度排序。然后我们有范围得对至少具有同样长度的字符串进行基数排序。在上述的例子中，按照长度排序后，分为3批不同长度的字符串，长度别为3,4,5。先对长度为5的字符串进行基数排序，并且只按照第5位字符进行排序即完成；然后对长度至少为4的两批字符串进行基数排序，并且只按照第4位字符进行排序即完成；最后最长度至少为3的所有字符串进行基数排序，分别按照第3,2,1位字符进行排序，最终得到的结果即排序结果。实现代码如下：
/**
* 不定长字符串基数排序
*/
public static void radixSort_ChaLenStr(String[] arr, int maxLen){
final int BUCKETS = 256;
ArrayList<String>[] wordsByLength = new ArrayList[maxLen + 1];
ArrayList<String>[] buckets = new ArrayList[BUCKETS];
for(int i=0; i<wordsByLength.length; i++){
wordsByLength[i] = new ArrayList<String>();
}
for(int i=0; i<BUCKETS; i++){
buckets[i] = new ArrayList<String>();
}
/**按字符串长度排序:桶排序**/
for(String s : arr){
wordsByLength[s.length()].add(s);
}
int ind = 0;
for(ArrayList<String> wordList : wordsByLength){
for(String s : wordList){
arr[ind++] = s;
}
}
/**基数排序**/
int startIndex = arr.length;
for(int pos = maxLen -1; pos >= 0; pos --){
startIndex -= wordsByLength[pos + 1].size();
for(int i=startIndex; i<arr.length; i++){
buckets[arr[i].charAt(pos)].add(arr[i]);
}
ind = startIndex;
for(ArrayList<String> bucket : buckets){
for(String s : bucket){
arr[ind++] = s;
}
bucket.clear();
}
}
}
针对nubmer的排序：
对于数组中的数字有已知的条件：大于0，最大数的位数有DIGS位（比如最大数为10000，DIGS为4）；
public static void radixSort(int[] nums, int DIGS) {
ArrayList<Integer>[] buckets = new ArrayList[10];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (int dig = 0; dig <= DIGS; dig++) {
// 入桶
for (int i = 0; i < nums.length; i++) {
int digNum = getDigNum(nums[i], dig);
buckets[digNum].add(nums[i]);
}
// 出桶
int ind = 0;
for (ArrayList<Integer> bucket : buckets) {
for (Integer num : bucket) {
nums[ind++] = num;
}
bucket.clear();
}
}
}
public static int getDigNum(int num, int dig) {
int div = new Double(Math.pow(10, dig)).intValue();
if (num >= div) {
return num / div % 10;
} else {
return 0;
}
}
计数基数排序
计数基数排序是基数排序的另一种实现，它避免使用ArrayList做桶。取而代之的是一个计数器，记录每个桶里会装多少个元素，将这个信息放在一个数组count中，于是count[k]就是桶k中元素的个数；然后基于count[k]计算出另一个数组offset，offset[k]的值为严格小于k的元素的个数，即。offset[k]告诉我们一个可以把k写进数组的有效位置，这一步做完后，offset[k]的值就加1，保证同一个桶里的元素被顺序地写入。为了比较和基数排序的区别，下图左边是基数排序，右边是计数基数排序的做法。
实现代码如下：
public static void countingRadixSort(String[] arr, int strLen) {
final int BUCKETS = 256;
int N = arr.length;
String[] buffer = new String[N];
String[] in = arr;
String[] out = buffer;
for (int pos = strLen - 1; pos >= 0; pos--) {
int[] count = new int[BUCKETS + 1];
// count为计数数组
for (int i = 0; i < N; i++) {
count[in[i].charAt(pos) + 1]++;
}
// count为位移数组
for (int b = 1; b <= BUCKETS; b++) {
count[b] += count[b - 1];
}
for (int i = 0; i < N; i++) {
out[count[in[i].charAt(pos)]++] = in[i];
}
// 替换in和out, 因为这一趟的输出为下一趟的输入
String[] tmp = in;
in = out;
out = tmp;
}
// 第奇数趟, out数组操作的是buffer数组, 并非输入数组arr, 所以需要将buffer数组复制会arr;
// 第偶数趟, out数组操作的是arr数组, 不需额外操作
if (strLen % 2 == 1) {
for (int i = 0; i < arr.length; i++) {
out[i] = in[i];
}
}
}
针对number的排序
对于数组中的数字有已知的条件：大于0，最大数的位数有DIGS位；
public static void countRadixSort(int[] nums, int DIGS) {
final int BUCKETS = 10;
// 输出结果
int[] out = new int[nums.length];
for (int pos = 0; pos <= DIGS; pos++) {
// 计数数组
int[] counts = new int[BUCKETS + 1];
for (int i = 0; i < nums.length; i++) {
int digNum = getDigNum(nums[i], pos);
counts[digNum + 1]++;
}
// 位移数组(通过出现次数的累计, 就可以得到排序的位置)
for (int k = 1; k <= BUCKETS; k++) {
counts[k] += counts[k - 1];
}
// 排序
for (int i = 0; i < nums.length; i++) {
int digNum = getDigNum(nums[i], pos);
out[counts[digNum]++] = nums[i];
}
// 替换本趟排序结果为下一趟输入
int[] tmp = nums;
nums = out;
out = tmp;
}
// 如果进行了奇数趟排序结束: 第奇数趟排序的结果实际存储在方法内部新建的数组中, 输入参数nums指向的数组元素并未改动;
// 如果进行了偶数趟排序: 第偶数趟排序的结果实际存储在输入参数nums指向的数组, 正确;
if ((DIGS + 1) % 2 == 1) {
for (int i = 0; i < nums.length; i++) {
out[i] = nums[i];
}
}
}
计数排序（number）
缺点：当max值很大时，浪费空间
优点：O(N)线性时间复杂度，实现简单
public static void countSort(int[] nums) {
if(nums.length <= 1){
return;
}
// 取最大值
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
// 计数数组
int[] count = new int[max + 1];
for (int num : nums) {
count[num]++;
}
// 排序
int ind = 0;
for (int i = 0; i < count.length; i++) {
for (int j = 0; j < count[i]; j++) {
nums[ind++] = i;
}
}
}
