下面我们将通过使用计数排序的思想来完成对上面数据的排序。

(先不谈负数)

计数排序

该排序的思路和它的名字一样…假设给定混乱数据为3013654219。

下面我们将通过使用计数排序的思想来完成对上面数据的排序。

(先不谈负数)

计数排序

该排序的思路和它的名字一样通过记录数据出现的次数来完成数据的排序。

我们默认实现的是升序。

这个很简单我们只需要遍历一遍原数组即可注意看代码后面的注释如下

(int

所以我们现在可以初步的来想一下用于统计次数的count数组大小是否可以直接使用原数据中最大的一个数据之后回答。

.....

以此类推当遍历完count数组之后数据的覆写就完成了也就完成了排序。

如下所示

对于上面的数据我们确实可以直接使用9作为count数组的最大值但是假设有这样一组数据

此时如果我们选用1009作为count数组的最大值那么0-998个数组空间根本不会被使用。

所以根据原数据的最大值来确定count数组的最大值是不合理的我们应该使用原数据中的

1009-1000

那么我在统计数据的出现次数的时候也就需要减去一个最小值比如1000-10000

1009-1000

那么我们在根据次数覆写数据的时候也就需要count的下标再加上原数据的最小值了。

01000

至此我们就完全解决了count数组大小的问题和对极端数据可能会造成空间浪费的问题。

#include

min];//减去最小值是为了防止最大值和最小值差距过大导致的空间浪费}//覆写原数组--排序过程int

0;for

其实这个问题根本不用回答我们先来用一组负数的数据跑一下看结果如何

int