计数排序

计数排序:

     原理感觉就像是在数数一样。

      1:处理出一个辅助数组Count[i] 来统计i前面有多少个数。

      2: 遍历Array  对应元素可以在Count 中找到对应的位置即可。

 

对于数组Array {4,3,5,8,5,6}. 其中给5弄上标记是为了显示其排序的稳定性。

步骤一:更新Count 数组。其中Count数组的容量为Array中最大的元素。这里就直接获得了是8

    Count[i] 表示 i这个值在Array中出现的次数。

步骤二:  更新Count 数组。

      Count[i]意义为 <=i的数的个数。

 步骤三:1:逆向遍历Array数组。(逆向是为了排序的稳定性)。

    2:根据Count[i]数组的含义。可以确定Array对应元素的位置。

  例如:

    当前是6。Count[6]含义是<=6的数据有几个。也就是说6排在Count[i]-1 这个位置。

    且Count[6]-- 其余值不变。这是为了当遇到下一个6的时候。下个6排在这个6的前面而 

    非同一个位置。并且排序是稳定的。

 后续步骤:接下来的元素同理做处理。

 

经过以上的操作就能获得结果Result数组。(作图有点失误。5忘记标号了。不过轻易就能知道的。)

关于其性能如何:

  首先可以做一个小小的分析(粗鄙之见)。就是数据跨度一定不能太大。因为他是从最小值一直数到最大值的。(样例的最小值是0,不要思维定式只能是0)

  不过算法本身确实是O(max(val))级别.其实际排序效果并不比快排之类的nlog(n)级别的好这也是可以理解的。比如数据跨度这一点。并且其空间复杂度也是该斟酌一下的。

一个是个数一个是值上的大小。

原文地址:https://www.cnblogs.com/Milkor/p/4433783.html