前面介绍的几种排序算法，都是基于不同位置的元素比较，算法平均时间复杂度理论最好值是θ(nlgn).
今天介绍一种新的排序算法，计数排序（Counting sort），计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：输入序列中数据取值范围有限，比如都是小于upperLimit的整数；
算法分3步实现：
1）遍历输入序列，统计不同取值的个数，放入计数数组；
2）遍历计数数组，计算不大于各个取值的个数，更新计数数组；
3）逆序遍历输入序列，结合计数数组中个数，将数据放到输出数组中。
（一）算法实现
protected void sort(int[] toSort) {
int[] result = new int[toSort.length];
int[] countingArray = new int[upperLimit];
for (int i = ; i < toSort.length; i++) {
countingArray[toSort[i]]++;
}
for (int i = ; i < countingArray.length; i++) {
countingArray[i] += countingArray[i - ];
}
for (int i = toSort.length - ; i >= ; i--) {
result[countingArray[toSort[i]] - ] = toSort[i];
countingArray[toSort[i]]--;
}
System.arraycopy(result, , toSort, , result.length);
}
Counting Sort
1）算法时间复杂是θ(n+k)，n表示输入序列中元素个数，k表示输入序列中元素取值集合的个数;
2）算法属于稳定排序；
3）算法不属于原地排序，需要额外空间存放计数数组和输出数组，空间复杂度是θ(n+k)；
4）算法不是比较排序算法。
（二）仿真结果
下面是计数排序和随机化排序的比较，从结果看，当k=O(n)时，计数排序时间复杂度更低。
**************************************************
Number to Sort is:2500
Array to sort is:{735805,621178,561545,362760,60951,337406,317120,378387,25311,115277...}
Cost time of 【CountingSort】 is(milliseconds):4
Sort result of 【CountingSort】:{177,418,611,924,1139,1752,2048,2221,2918,3340...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):0
Sort result of 【RandomizedQuickSort】:{177,418,611,924,1139,1752,2048,2221,2918,3340...}
**************************************************
Number to Sort is:25000
Array to sort is:{435929,221392,407142,872904,594585,726112,958590,976368,570033,848066...}
Cost time of 【CountingSort】 is(milliseconds):5
Sort result of 【CountingSort】:{24,42,79,134,142,257,268,462,503,544...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):2
Sort result of 【RandomizedQuickSort】:{24,42,79,134,142,257,268,462,503,544...}
**************************************************
Number to Sort is:250000
Array to sort is:{426400,121941,600931,85753,455109,650154,341754,478839,921893,648842...}
Cost time of 【CountingSort】 is(milliseconds):16
Sort result of 【CountingSort】:{0,2,6,23,33,34,35,38,41,46...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):28
Sort result of 【RandomizedQuickSort】:{0,2,6,23,33,34,35,38,41,46...}
**************************************************
Number to Sort is:2500000
Array to sort is:{26177,919623,668931,41665,236093,656020,473433,258087,659468,419426...}
Cost time of 【CountingSort】 is(milliseconds):206
Sort result of 【CountingSort】:{0,0,0,2,3,3,4,4,5,5...}
Cost time of 【RandomizedQuickSort】 is(milliseconds):334
Sort result of 【RandomizedQuickSort】:{0,0,0,2,3,3,4,4,5,5...}
相关代码：
package com.cnblogs.riyueshiwang.sort;
import java.util.Arrays;
public class CountingSort extends abstractSort {
private int upperLimit;
public CountingSort(int upperLimit) {
this.upperLimit = upperLimit;
}
@Override
protected void sort(int[] toSort) {
int[] result = new int[toSort.length];
int[] countingArray = new int[upperLimit];
for (int i = 0; i < toSort.length; i++) {
countingArray[toSort[i]]++;
}
for (int i = 1; i < countingArray.length; i++) {
countingArray[i] += countingArray[i - 1];
}
for (int i = toSort.length - 1; i >= 0; i--) {
result[countingArray[toSort[i]] - 1] = toSort[i];
countingArray[toSort[i]]--;
}
System.arraycopy(result, 0, toSort, 0, result.length);
}
public static void main(String[] args) {
for (int j = 0, n = 2500; j < 4; j++, n = n * 10) {
System.out
.println("**************************************************");
System.out.println("Number to Sort is:" + n);
int upperLimit = 1000000;
int[] array = CommonUtils.getRandomIntArray(n, upperLimit);
System.out.print("Array to sort is:");
CommonUtils.printIntArray(array);
int[] array1 = Arrays.copyOf(array, n);
new CountingSort(upperLimit).sortAndprint(array1);
int[] array2 = Arrays.copyOf(array, n);
new RandomizedQuickSort().sortAndprint(array2);
}
}
}
CountingSort.java