计数排序

首先，让我们了解什么是计数排序。 计数排序： 计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

排序过程： 假设输入的线性表L的长度为n，L=L1,L2,…,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,…Sk}；则计数排序可以描述如下：

1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)； 2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。

简单理解： 一个序列中有n个元素，通过序列中每一个元素小于其的元素的个数来确定另一个序列的下标，然后这个元素就是该下标上的值。当然这种情况下，你要考虑当这个序列有相同的元素应该怎么办？

好了，了解了以上内容来看看我写的代码吧！