非比较排序-计数排序

1.计数排序

前面学习了归并排序，快速排序时间复杂度为O(n*logn)而有没有比这更快的排序算法呢？当然是有的那就是计数排序，首先计数排序并不是比较排序算法，而是利用数组来实现的一种算法，想象一下这样一个场景，假如给数组{1，4，5，1，3}做一个排序,我们可以看出其中最大的值就是5，但是怎么利用数组实现排序呢？我们知道数组是一组连续的地址空间，且可以通过下标进行随机访问，数组有下标是有序的，我们可以利用下标来实现排序。

首先我们知道数组{1，4，5，1，3}中最大是5，那我们至少需要一个下标能够达到5吧，所以我们定义一个长度为最大值加1长度的计数数组，也就是6，同时给所有下标的值默认为0，然后遍历要排序的数组{1，4，5，1，3}，每拿到一个数，就在计数数组对应的下标加1，例如第一次遍历为1，那么就在计数数组下标为1的位置加1，当然如果出现多次依然是累加，比如第一次出现了1，计数数组下标1的位置加1，加1表示出现了1次，下一次又出现了一次1那么还是加1，此时计数下标为1的位置值就是2，也就是出现了2次。(看下面图)

最后我们可以看到计数数组的值为{0，2，0，1，1，1}，此时我们只需要将计数数组中对应下标进行输出即可，比如计数数组中下标为0的值为0，此时就是输出0次，而1出现两次，那么输出两次1即可。

java代码实现如下所示

虽然上面代码实现了排序，但是存在很多问题。

1.如果要排序的数组是这样的数组{90，93，92，92，95},难道我们还是要根据最大值为95开一个长度为96的计数数组吗？这样就大大浪费了空间了，我们采用的方式就是用最大值减最小值+1，然后根据最小值做为偏移量进行计算在计数数组中为位置，比如90放的位置就是90-最小值90，也就是0的位置，而93则是93-90，也就是3的位置。我们更改代码后实现如下。

2.我们解决了数组值不是从0开始浪费空间的问题，下面就是如果是负数或者小数我们应该怎么解决呢？如果存在负数的情况，那么我们找到最小的负数，给负数加上一个数，使得他变成正数，当然你不可能只加这一个地方，应该是这个数组每一位都要加上这个值，这样才能保证不影响大小，但是你不能加了后面就不管了吧，所以在把结果放到结果数组中时，我们应该减去之前加的数；同理如果存在小数的情况，我们只需要找到最小的那个值乘以一个数，使得变为整数，然后其余位置全部乘以这个数即可，当然最后将值给返回数组中时，要除以之前乘以的数。

3.计数排序怎么实现稳定排序呢？你想想一下我们如果有两个5，我们只是在计数数组下标为5的位置加了2次，记录了出现的次数，我们实际上根本不知道这个5究竟是哪个数，就比如期末考试吧，如果小红考了95，小阳也考了95，那么我们只是在对应下标上加了2次，根本不知道是小红还是小阳。这个问题怎么解决呢？下面的内容有点烧脑，前方高能。

首先假定我们有这样的考试成绩，小红94分，小灰91分，小绿91分，小白92分，也就是要排序的数组为{94，91，91，92}，然后可以得到计数数组为{2，1，0，1}，然后把计数数组变形成下面的样子。

变形后的计数数组实际上就是从下标1开始每一位都加上前面的值，比如下标1的数1加上上一位下标0的数2就是3，下标2的数0加上下标1的数3也就是3，下标3的数1加上下标2的数3就是4。

这样做是为什么呢？这样就可以知道对应每个学生考试成绩在第几名了，如果我们再把名次减1，也就是实际上最终返回数组中所在的位置，比如小白92分，我们可以通过92-91（最小值）=1，然后根据1找到，他在计数数组变形版的下标为1的位置，也就是第三名，然后我们再把3减去1，也就是他应该存放在最终返回数组中的位置。同理如果是小绿我们可以知道他是在计数数组变形中的下标为0的位置，也就是第二名，然后我们减去1，也就是应该存放在下标为1的位置，那么小灰呢？小灰我们知道他是91分那么这样我们就可以知道他在计数数组变形中的下标为0的位置，因为之前小绿已经减了一次1，所以现在他是第一名，且我们再减1，那么他就应该存放在下标为0的位置。

需要注意的是我们在最后遍历的时候，必须倒着遍历。为什么必须要倒着遍历，如果不倒着遍历小灰和小绿的位置就发生了变化，也就不再是稳定的排序了。

java代码实现如下。

我们来看看计数排序的时间复杂度和空间复杂度，首先我们找最大值和最小值执行了n次，然后计数数组产生值有需要遍历n次，也就是O(2*n)，然后我们再变形了一次计数数组，就是k次，最后我们又遍历了一次原数组，所以就是O(3*n+k)，然后根据大O表示法，我们去掉一个常数阶，可以得到时间复杂度为O(n+k)，那么空间复杂度呢？我们返回数组定义了一个和原始数组一样长的也就是n，然后定义了一个计数数组k，所以就是O(n+k)，如果不考虑结果数组就是O(n)。