前面介绍的几种排序算法，都是基于不同位置的元素比较，算法平均时间复杂度理论最好值是θ(nlgn).

今天介绍一种新的排序算法，计数排序（Counting sort），计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：输入序列中数据取值范围有限，比如都是小于upperLimit的整数；

算法分3步实现：

1）遍历输入序列，统计不同取值的个数，放入计数数组；

2）遍历计数数组，计算不大于各个取值的个数，更新计数数组；

3）逆序遍历输入序列，结合计数数组中个数，将数据放到输出数组中。

（一）算法实现

 

1 protected void sort(int[] toSort) { 2         int[] result = new int[toSort.length]; 3         int[] countingArray = new int[upperLimit]; 4         for (int i = 0; i < toSort.length; i++) { 5             countingArray[toSort[i]]++; 6         } 7         for (int i = 1; i < countingArray.length; i++) { 8             countingArray[i] += countingArray[i - 1]; 9         }10 11         for (int i = toSort.length - 1; i >= 0; i--) {
     12             result[countingArray[toSort[i]] - 1] = toSort[i];13             countingArray[toSort[i]]--;14         }15 16         System.arraycopy(result, 0, toSort, 0, result.length);17     }

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...}

相关代码：

1 package com.cnblogs.riyueshiwang.sort; 2  3 import java.util.Arrays; 4  5 public class CountingSort extends abstractSort { 6  7     private int upperLimit; 8  9     public CountingSort(int upperLimit) {10         this.upperLimit = upperLimit;11     }12 13     @Override14     protected void sort(int[] toSort) {15         int[] result = new int[toSort.length];16         int[] countingArray = new int[upperLimit];17         for (int i = 0; i < toSort.length; i++) {18             countingArray[toSort[i]]++;19         }20         for (int i = 1; i < countingArray.length; i++) {21             countingArray[i] += countingArray[i - 1];22         }23 24         for (int i = toSort.length - 1; i >= 0; i--) {25             result[countingArray[toSort[i]] - 1] = toSort[i];26             countingArray[toSort[i]]--;27         }28 29         System.arraycopy(result, 0, toSort, 0, result.length);30     }31 32     public static void main(String[] args) {33         for (int j = 0, n = 2500; j < 4; j++, n = n * 10) {34             System.out35                     .println("**************************************************");36             System.out.println("Number to Sort is:" + n);37             int upperLimit = 1000000;38             int[] array = CommonUtils.getRandomIntArray(n, upperLimit);39             System.out.print("Array to sort is:");40             CommonUtils.printIntArray(array);41 42             int[] array1 = Arrays.copyOf(array, n);43             new CountingSort(upperLimit).sortAndprint(array1);44 45             int[] array2 = Arrays.copyOf(array, n);46             new RandomizedQuickSort().sortAndprint(array2);47         }48     }49 }