简述
计数排序适用于对一定范围内的元素进行排序。
它的思路就是创建一个范围性的计数数组，用下标去对应元素的值，有几个元素，相应下面命中几次。然后根据元素命中次数对下标值进行一次输出，得到的序列就是有序的序列。
它是不需要进行元素比较。
注意：
- 当数列最大和最小值差距过大时，不适合使用计数排序
- 当数列元素不是整数时，也不适合用计数排序
复杂度
| 名称 | 最好 | 平均 | 最差 | 空间 | 稳定性 |
| 计数排序 | n+m | n+m | n+m | m | 是 |
初步实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
vector<int> CountSort(vector<int> &array) { //获取数列的最大值 int max = 0; for(auto elem : array) if (elem > max) max = elem; //创建统计数组 vector<int> countArray(max + 1); //遍历数组，填充统计数组 for(auto elem : array) countArray[elem]++; //遍历统计数组 int index = 0; vector<int> sortedArray(array.size()); for (int i = 0; i < max + 1; ++i) for (int j = 0; j < countArray[i]; ++j) sortedArray[index++] = i; return sortedArray; } |
优化版1.0
由于我们在实现统计数组的时候，是以待定排序数组中值最大的元素为标准，创建统计数组的。这样就会有一个不太好的地方，比如：
数组里只有10多个元素，但是取值范围是：
【80，100】之间，按上个实现去设计的话，我们需要创建一个差不多能包括90多个元素空间大小的统计数组，这是完全没有必要的。解决方法就是不再以输入序列中元素的最大值作为统计数组的长度，而是
最大值-最小值+1作为统计数组的长度。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
vector<int> CountSort1(vector<int>& array) { //获取数列最大值和最小值 int max = 0; int min = 0; for (auto elem : array) { if (elem > max) max = elem; if (elem < min) min = elem; } //创建统计数组 vector<int> countArray(max - min + 1); //遍历数组，填充统计数组 for (auto elem : array) countArray[elem]++; //遍历统计数组 int index = 0; vector<int> sortedArray(array.size()); for (int i = 0; i < max - min + 1; ++i) for (int j = 0; j < countArray[i]; ++j) sortedArray[index++] = i + min; return sortedArray; } |
算法导论
计数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且都是小于max_val:
- 首先对A进行计数。对每一个元素A[i]，将它出现的次数存放在CounterArray[A[i]]中
- 然后对CounterArray累加，得出A[i]应该在结果序列中排多少位
- 最后在结果数组中直接放置A[i]（根据它的排位）
- 时间复杂度 O(n)
- 空间复杂度 O(n)
这里必须对整数才能采取计数排序。由static_assert(...,...)确保
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
template<typename Iterator> void count_sort(const Iterator begin,const Iterator end,const typename std::iterator_traits<Iterator>::value_type& max_val) { typedef typename std::iterator_traits<Iterator>::value_type T;// 迭代器指向对象的值类型 static_assert(std::is_integral<T>::value, "sequence to be sorted must be integer!"); //必须针对整数进行计数排序 auto size=std::distance(begin,end); if(size <=1) return; std::vector<T> CounterArray(max_val+1); //存放计数结果 std::vector<T> ResultArray(size); //暂存排序结果 std::size_t n=0; while(begin+n!=end) //计个数 { CounterArray.at(*(begin+n))++; n++; } for(std::size_t i=1;i<CounterArray.size();i++)//计排位数 { CounterArray.at(i)+=CounterArray.at(i-1); } int index=ResultArray.size()-1; while(index>=0) { auto data=*(begin+index); //待排序的元素 T less_data_num=CounterArray[data]-1; //比它小的元素的个数 ResultArray[less_data_num]=data; //直接定位 CounterArray[data]--; //此行为了防止重复元素的定位 index--; } std::copy(ResultArray.begin(),ResultArray.end(),begin); } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 匹配_有限自动机字符串匹配算法10/13
- ♥ 排序_基数排序09/04
- ♥ 查找_二分查找05/09
- ♥ 排序_快速排序05/08
- ♥ 数学知识模板03/09
- ♥ 算法特点、哈希表06/29
热评文章
- 匹配_KMP模式匹配算法：一 0
- 动态规划_最长公共子序列 0
- 基础算法模板 0
- 排序_基数排序 0
- 数据结构模板 0
- 排序_归并排序 0