【【算法导论之四】计数排序】1. 计数排序的思想
我们之前接触过的例如：插入排序，归并排序，快速排序，堆排序等都是基于集合元素之间的比较这一基本的思想，它们执行的时间复杂度最优是趋于O(nlgn)，而计数排序的运行机制不是基于集合元素之间的大小比较，什么？？？不做比较还能区分出元素之间的大小？是啊，算法就是这么伟大，我刚看它的时候也是激动不已呢。
计数排序的基本思想是：对每一个输入元素 x ，确定出小于 x 的元素个数。有了这一信息，就可以把 x 直接放到它在最终输出数组的位置上。
2. 计数排序的空间代价，假设原数组为：a[ 1...n ]
数组c[ k ] ：提供临时存储区。这里 k 的定义为：a数组中每个元素都是介于 0 到 k 之间的整数，也可以将 k 想象成数组a中的最大值。
数组b[ n ] ：存放排序结果。
注：这是一般的计数排序的空间消耗，我们可以通过一种方式，将这里存放排序结果的b数组省去，直接将最终排序的结果存在原数组a中，这个会在下面提到。
3. 计数排序的适用条件
计数排序是一个算法时间复杂度为θ( n )的排序方法，它适用于小范围集合的排序。这里的小范围是指 k = O(n)，即 k 值不能太大。比如：我们要对全国高考学生的数学成绩进行排名，这里我们已经知道数学成绩是介于：0-150之间的，即这里的 k = 150 的，而高考学生的数量在900多万左右，这样的情况下可以达到很好的性能。
4. 计数排序伪代码
counting-sort(a,b,k)
for i<-0 to k
do c[i] <- 0
for j<-0 to length(a)
do c[a[j]] <- c[a[j]] + 1
for i<-1 to k
do c[i] <- c[i] + c[i-1]
for j <- length[a]-1 down to 0
do b[c[a[j]]] <- a[j]
c[a[j]] <- c[a[j]] -15. 计数排序 java实现代码及运行结果
public class CountSort {
public static void count_sort(int[] a, int[] b, int k){
int[] c = new int[k+1];
// 对计数数组c[i]进行初始化0
for(int i = 0 ;
i
程序运行结果：
文章图片
6. 对计数排序算法的改进
上面我们提到了，为了执行计数排序算法，需要消耗一个等大小的数组 b[ 1...n ] ， 我们可以通过某种方式来避免使用数组b。
比如：数组 a 中的元素为： 32421
数组 c 执行完 for i <- 0 to kc[ i ]++为：[[0][1][2][1][1]]
01234
这里 c 的下标代表的正是 a数组中的元素，而 c[ i ] 则代表的是它在数组中出现的次数，我们可以利用这个关系直接将最终结果保存在数组 a 中。
关键代码如下：
public static void count_sort(int[] a,int k){
int[] c = new int[k+1];
// 对计数数组c[i]进行初始化0
for(int i = 0 ;
i
注意上面没有了：for i <-1 to kc[i] <- c[i] + c[i-1] 了。
运行结果：
文章图片
坚持每天的学习，加油！！！！
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 算法导论计数排序实现