c++|算法导论第八章 -- 计数排序 and|data|structure|algorithm

1.算法基本思想：对于在待排序的数组里面的数字，记录小于它的元素的个数，那么记录下来的这个数字就是它在输出数组里面的位置了
这里假设元素是互异的。
2.如果元素不互异，那么就要对算法里面的一个记录数组作一些操作，以便保持算法的正确性。

代码如下：

countSort.h

#ifndef COUNTSORT_H #define COUNTSORT_H#include #include std::vector countSort(std::vector&); void printVector(std::vector&); int getMax(std::vector&); #endif

其中，第一个函数是算法，第二个函数方便打印数组，第三个函数得到数组中的最大值
为何要得到最大值：在下面解释。

#include "countSort.h"int getMax(std::vector& target)//遍历数组，找到最大值 { int max = 0; for (std::vector::size_type i = 0; i != target.size(); ++i) { if (target[i] > max) { max = target[i]; } } return max; }void printVector(std::vector& target)//打印数组 { for (std::vector::size_type i = 0; i != target.size(); ++i) { std::cout << target[i] << " "; } std::cout << std::endl; }std::vector countSort(std::vector& target)//计数排序 { typedef std::vector::size_type index; int maxElement = getMax(target); std::vector result(target.size(),0); //新开两个数组，一个用来记录元素的个数 std::vector count(maxElement + 1,0); //另外一个用来装结果 for (index i = 0; i != target.size(); ++i)//解释点1 { count[target[i]] += 1; } for (index i = 1; i!= count.size(); ++i)// 解释点2 { count[i] += count[i-1]; } for (index i = 0; i != target.size(); ++i)//解释点3 { result[count[target[i]] - 1] = target[i]; count[target[i]] -= 1; } return result; }

在计数排序中，我们需要两个临时数组来辅助，第一个数组count是用来记录每一个元素出现的个数，并且要对这个数组进行一定的运算得到
原来数组内小于等于这个数组下标数字的元素的个数。就相当于：count这个数组的下标表示可能在原来数组中的元素，而存储在count
中的数字是对应下标数字出现的次数。
例： count[5] = 7：代表在原数组中，5这个数字出现了7次。
解释点1：
遍历要排序的数组，然后把数组里面的元素出现的次数记录在辅助数组相应的位置
解释点2：
把辅助数组重构：从第二个元素开始，把当前元素加上上一个元素的值，相当于：在待排序的数组里，小于这个下标的元素的个数。
解释点3:
从原始数组的第一个元素开始，用这个元素在辅助数组里面找到小于这个值的元素的个数，然后把原始数组的当前元素赋值到输出数组的相应位置。
因为待排序的数组元素个数已经少一个了，并且考虑原始数组里面有重复元素的情况，那么就要把当前辅助数组相应位置的值减1，表示等于
这个下标的值的元素已经少了一个。
并且在辅助数组中，元素的值必然是大于等于0的，等于0没有关系，因为不会再索引到这个值。

main.cpp

#include "countSort.h"int main() { int a[11] = {6,0,2,0,1,3,4,6,1,3,100000}; std::vector v(a,a+11); std::vector r = countSort(v); printVector(r); return 0; }

可以得到正确的排序结果。

缺点：相对于其他原址排序的算法（堆排序，快排），这个排序算法会用到额外的空间，并且如果数组中的最大值很大很大的时候，那么辅助数组
的利用率会很低，比如说：
我们有一个待排序的数组：［1000000，1］，就两个元素，但是最大值是1000000，所以辅助数组的长度就是1000001，用上面的方法操作
这个数组的时间会上升很多。按照书上的伪代码：k这个值是可以被辅助数组索引到的，那么为了让程序不会抛出out_of_range 的异常的话，
那么就只能找出原始数组里面的最大值，并且把辅助数组的长度初始化为这个最大值加1，才能保证count[ target[ i ] ]这一语句的正确性。
并且待排序的数组里面的元素只能是大于等于0的整数（保证能正确索引）

【c++|算法导论第八章 -- 计数排序】