假设20个随机整数的值如下所示。9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9。
在0到10之间取值。数组定义大小为取值的最大范围
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作。
例如第1个整数是9，那么数组下标为9的元素加1。
第2个整数是3，那么数组下标为3的元素加1。
继续遍历数列并修改数组……，最终，当数列遍历完毕时，数组的状态如下。
该数组中每一个下标位置的值代表数列中对应整数出现的次数。
有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10显然，现在输出的数列已经是有序的了。
使用场景它适用于一定范围内的整数排序。在取值范围不是很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn)的排序。
当数列最大和最小值差距过大时，并不适合用计数排序。
当数列元素不是整数时，也不适合用计数排序。
简单示例计数类ClassPHA.YX.Arithmetic.CountSortExtends%RegisteredObject
{
Methodsort(arrayAsPHA.YX.Arithmetic.Array)
{
/*1.得到数列的最大值*/
#dimmaxas%Integer=array.get(0)
fori=1:1:(array.length()-1){
if(array.get(i)max){
smax=array.get(i)
}
}
/*2.根据数列最大值确定统计数组的长度*/
#dimcountArrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
dcountArray.init(max+1)
/*3.遍历数列，填充统计数组*/
fori=0:1:(array.length()-1){
if(countArray.get(array.get(i))=""){
dcountArray.set(array.get(i),0)
}else{
dcountArray.set(array.get(i),(+countArray.get(array.get(i))+1))
}
}
b;countArray
/*4.遍历统计数组，输出结果*/
#dimindexas%Integer=0
#dimsortedArrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
dsortedArray.init(array.length())
fori=0:1:(countArray.length()-1){
forj=0:1:(countArray.get(i)){
dsortedArray.set(index,i)
sindex=index+1
}
}
b;sortedArray
qsortedArray
}
}
调用///w##class(PHA.YX.Arithmetic).CountSort()
ClassMethodCountSort()
{
#dimarrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
darray.init(13)
darray.insert(0,4)
darray.insert(1,4)
darray.insert(2,6)
darray.insert(3,5)
darray.insert(4,3)
darray.insert(5,2)
darray.insert(6,8)
darray.insert(7,1)
darray.insert(8,7)
darray.insert(9,5)
darray.insert(10,6)
darray.insert(11,0)
darray.insert(12,10)
#dimcountSortasPHA.YX.Arithmetic.CountSort=##class(PHA.YX.Arithmetic.CountSort).%New()
sarray=countSort.sort(array)
darray.output()
q""
}
BREAKzsort+30^PHA.YX.Arithmetic.CountSort.1
DHC-APP3e1g
0
1
2
3
4
4
5
5
6
6
7
8
9
10
优化问题我们只以数列的最大值来决定统计数组的长度，其实并不严谨。例如下面的数列。95，94，91，98，99，90，99，93，91，92。
这个数列的最大值是99，但最小的整数是90。如果创建长度为的数组，那么前面从0到89的空间位置就都浪费。
解决以最大值减去最小值的差作为数组的长度。
以刚才的数列为例，统计出数组的长度为99-90+1=10，偏移量等于数列的最小值90。
优化版本计数类MethodoptimizeSort(arrayAsPHA.YX.Arithmetic.Array)
{
/*1.得到数列的最大值和最小值，并算出差值d*/
#dimmaxas%Integer=array.get(0)
#dimminas%Integer=array.get(0)
fori=1:1:(array.length()-1){
if(array.get(i)max){
smax=array.get(i)
}
if(array.get(i)min){
smin=array.get(i)
}
}
#dimdas%Integer=max-min
/*2.创建统计数组并统计对应元素个数*/
#dimcountArrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
dcountArray.init(d+1)
fori=0:1:(array.length()-1){
if(countArray.get((array.get(i)-min))=""){
dcountArray.set((array.get(i)-min),1)
}else{
dcountArray.set((array.get(i)-min),(+countArray.get((array.get(i)-min))+1))
}
}
b;2countArray
/*3.统计数组做变形，后面的元素等于前面的元素之和*/
fori=1:1:countArray.length-1{
dcountArray.set(i,(countArray.get(i)+countArray.get(i-1)))
}
b;3countArray
/*4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组*/
#dimsortedArrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
dsortedArray.init(array.length())
fori=(countArray.length()-1):-1:0{
sarrayMin=array.get(i)-min
scountMin=countArray.get(arrayMin)-1
dsortedArray.set(countMin,array.get(i))
dcountArray.set(arrayMin,countMin)
}
b;sortedArray
qsortedArray
}
调用///w##class(PHA.YX.Arithmetic).OptimizeCountSort()
ClassMethodOptimizeCountSort()
{
#dimarrayasPHA.YX.Arithmetic.Array=##class(PHA.YX.Arithmetic.Array).%New()
darray.init(10)
darray.insert(0,95)
darray.insert(1,94)
darray.insert(2,91)
darray.insert(3,98)
darray.insert(4,99)
darray.insert(5,90)
darray.insert(6,99)
darray.insert(7,93)
darray.insert(8,91)
darray.insert(9,92)
#dimcountSortasPHA.YX.Arithmetic.CountSort=##class(PHA.YX.Arithmetic.CountSort).%New()
sarray=countSort.optimizeSort(array)
darray.output()
q""
}
DHC-APPw##class(PHA.YX.Arithmetic).OptimizeCountSort()
90
91
91
92
93
94
95
98
99
99
时间复杂度代码第1、2、4步都涉及遍历原始数列，运算量都是n，第3步遍历统计数列，运算量是m，所以总体运算量是3n+m，去掉系数，时间复杂度是O(n+m)。
空间复杂度至于空间复杂度，如果不考虑结果数组，只考虑统计数组大小的话，空间复杂度是O(m)。
大姚姚鑫