第十六章 Caché 算法与数据结构 计数排序
第十六章 Caché 算法与数据结构 计数排序
定义
假设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)的排序。
当数列最大和最小值差距过大时，并不适合用计数排序。
当数列元素不是整数时，也不适合用计数排序。
简单示例
计数类
Class PHA.YX.Arithmetic.CountSort Extends %RegisteredObject
{
Method sort(array As PHA.YX.Arithmetic.Array)
{
/* 1.得到数列的最大值 */
#dim max as %Integer = array.get(0)
for i = 1 : 1 : (array.length() - 1) {
if (array.get(i) > max){
s max = array.get(i)
}
}
/* 2.根据数列最大值确定统计数组的长度 */
#dim countArray as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d countArray.init(max + 1)
/* 3.遍历数列，填充统计数组 */
for i = 0 : 1 : (array.length() - 1) {
if (countArray.get(array.get(i)) = ""){
d countArray.set(array.get(i), 0)
}else{
d countArray.set(array.get(i), (+countArray.get(array.get(i)) + 1))
}
}
b ;countArray
/* 4.遍历统计数组，输出结果 */
#dim index as %Integer = 0
#dim sortedArray as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d sortedArray.init(array.length())
for i = 0 : 1 : (countArray.length() - 1) {
for j = 0 : 1 : (countArray.get(i) ){
d sortedArray.set(index, i)
s index = index + 1
}
}
b ;sortedArray
q sortedArray
}
}
调用
/// w ##class(PHA.YX.Arithmetic).CountSort()
ClassMethod CountSort()
{
#dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d array.init(13)
d array.insert(0,4)
d array.insert(1,4)
d array.insert(2,6)
d array.insert(3,5)
d array.insert(4,3)
d array.insert(5,2)
d array.insert(6,8)
d array.insert(7,1)
d array.insert(8,7)
d array.insert(9,5)
d array.insert(10,6)
d array.insert(11,0)
d array.insert(12,10)
#dim countSort as PHA.YX.Arithmetic.CountSort = ##class(PHA.YX.Arithmetic.CountSort).%New()
s array = countSort.sort(array)
d array.output()
q ""
}
<BREAK>zsort+30^PHA.YX.Arithmetic.CountSort.1
DHC-APP 3e1>g
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。如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费。
解决
以最大值减去最小值的差作为数组的长度。
以刚才的数列为例，统计出数组的长度为99-90+1=10，偏移量等于数列的最小值90。
优化版本
计数类
Method optimizeSort(array As PHA.YX.Arithmetic.Array)
{
/* 1.得到数列的最大值和最小值，并算出差值d */
#dim max as %Integer = array.get(0)
#dim min as %Integer = array.get(0)
for i = 1 : 1 : (array.length() - 1) {
if (array.get(i) > max){
s max = array.get(i)
}
if (array.get(i) < min){
s min = array.get(i)
}
}
#dim d as %Integer = max - min
/* 2.创建统计数组并统计对应元素个数 */
#dim countArray as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d countArray.init(d + 1)
for i = 0 : 1 : (array.length() - 1) {
if (countArray.get((array.get(i)- min)) = ""){
d countArray.set((array.get(i) - min), 1)
}else{
d countArray.set((array.get(i) - min), (+countArray.get((array.get(i) - min)) + 1))
}
}
b ;2 countArray
/* 3.统计数组做变形，后面的元素等于前面的元素之和 */
for i = 1 : 1 : countArray.length - 1 {
d countArray.set(i , (countArray.get(i) + countArray.get(i - 1)))
}
b ;3 countArray
/* 4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组 */
#dim sortedArray as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d sortedArray.init(array.length())
for i = (countArray.length() - 1) : -1 : 0 {
s arrayMin = array.get(i) - min
s countMin = countArray.get(arrayMin) - 1
d sortedArray.set(countMin, array.get(i))
d countArray.set(arrayMin, countMin)
}
b ;sortedArray
q sortedArray
}
调用
/// w ##class(PHA.YX.Arithmetic).OptimizeCountSort()
ClassMethod OptimizeCountSort()
{
#dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
d array.init(10)
d array.insert(0,95)
d array.insert(1,94)
d array.insert(2,91)
d array.insert(3,98)
d array.insert(4,99)
d array.insert(5,90)
d array.insert(6,99)
d array.insert(7,93)
d array.insert(8,91)
d array.insert(9,92)
#dim countSort as PHA.YX.Arithmetic.CountSort = ##class(PHA.YX.Arithmetic.CountSort).%New()
s array = countSort.optimizeSort(array)
d array.output()
q ""
}
DHC-APP>w ##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)。