计数排序不是基于元素比较,而是利用数组下标来确定元素的正确位置。计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。
算法思路
计数排序的算法思路是定义一个大小为序列最大值-最小值的大小的数组,遍历每一个元素,将其映射到数组中,例如最大值和最小值相差10,就定义一个大小为10的数组,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。
比如第一个整数是9,那么数组下标为9的元素加1:
最终,数列遍历完毕时,数组中的每一个值,代表了数列中对应整数的出现次数。有了这个统计结果,排序就很简单了,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次。
不稳定的计数排序
算法的实现可以分为三个步骤
稳定的计数排序
稳定的基数排序跟上者的差别是在,如果值相同,则遵循原表固有顺序。
算法思路
算法的具体思路是在遍历完序列映射到数组中后,例如下图是已经映射好的数组。原序列为{90,99,95,95,94}
在第二个下标开始,加上前面元素的和,例如上图第一个下标为1,那么第二个下标的数值就为本身的0加上前面的1等于1。第三个就等于第三加上前面的数的总个数,以此类推。
这个数值其实就代表了映射的元素在原数组中因该在的位置,整个数组中有用的下标就只有0,4,5,9四个下标是由代表有数值的,其他都是空的,下标为0的数值为1即使第一个数字,下标为4的数值为2即第二个数,下标为5的数值为4,我们看到95是有两个数,所以是第3的数和第4的数,最后一个为第五的数。
理解了上面后,在赋值给原数组的过程中,从后往前遍历,例如原序列为{90,99,94,95,95},第一个数为95,在映射的数组中下标为4,即原数组array[4]=95,然后4-1=3,即如果有第二个95,它的位置就是3,然后第二个数是95,这时候下标为3,即array[3]=95,依照这种算法随后得到的结果就为{90,94,95,95,99},而且是稳定的排序。
代码的实现分为两步
第一步在得到了映射后的数组countArray后,从第二个下标开始,加上前面的数的个数,即countArray[i] = countArray[i-1]+countArray[i]。
第二步是定义一个数组用于存储,countArray[i-min]即映射数组的值,即第几个元素,例如第5个元素,那么下标就为4,所以要-1,然后countArray[i-min]自减。
int[] sortArray = new int[array.length]; for (int i:array){ sortArray[countArray[i-min]-1] = i; countArray[i-min]--; }