一、计数排序算法
计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组，数组的下标对应待排序的数字。然后根据新数组的下标来获得正确的顺序。就像给每个位置按数字顺序做好标记，然后把对应数组放入其中，最后把下标打印出来即可。计数排序只适合数量较少的正整数排序。其算法复杂度接近于：O(N + K)
步骤是：
- 找到待排序中最大和最小的元素；
- 新建一个计数数组，长度为最大与最小值的差值+1；
- 遍历待排序数组，将数字与计数数组下标对应，按出现次数做标记；做对应时为了减少数组长度，可以用下标减去最小值；
- 反向取出数据，按出现的次数逐个追加到输出数组中。
二、计数排序算法执行过程分析：
三、计数排序代码标准版实现
标准版移植自C语言版，得到最大最小值，再新建空的计数数组，长度为差值+1，再统计对应下标的数字，最后将计数数组逐个还原打印出来。
四、计数排序代码简版
JS语言非常灵活好用，并不需要想C语言或Java等提前指定数组的大小，因此也没有必要利用减少min来标记数据。整体思路就是利用下标统计对应的数字，然后按照下标取出数字来即可。代码量非常少，也很简单易懂。
分享到:
