标签:计数排序

计数排序CountingSort

发表于3年前(Dec 24, 2014 10:18:15 AM)  阅读 731  评论 0

分类: Java 算法 排序

标签: countingsort 计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。

计数排序算法的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。例如,如果输入序列中只有17个元素的值小于x的值,则x可以直接存放在输出序列的第18个位置上。当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,因此,上述方案还要作适当的修改。

计数排序的时间复杂度为O(n),当然是有条件的。计数排序不是原地排序。