计数排序:时间复杂度为O(n)、有稳定性

基础条件假设: 假设n个输入元素中每一个都是在0-k区间的一个整数。

计数排序的基本思想: 对每一个输入元素x,确定小于x的元素个数。这样可以将x直接放在输出数组中的位置上。

伪代码:
计数排序:时间复杂度为O(n)、有稳定性
注:
1、可以在第二个方框后直接利用各元素个数写出排序后数组,但这样丢失了稳定性;
2、而按以上伪代码方式,统计小于或等于下标的元素个数,后逆序处理数组A中个元素位置,则保持了稳定性

计数排序的性质:
1、时间复杂度为O(n)。
2、为稳定排序。
计数排序:时间复杂度为O(n)、有稳定性
参考资料: 算法导论 8.2节 计数排序

总结:

1、注意伪代码中多次数组值做下标的使用方法。
2、计数排序为稳定排序,时间复杂度为O(n)。