简述
基数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且不超过RADIXWITH位（有模板的RADIXWITH参数指定）：
- 首先对A中所有元素按照个位数大小进行排序（原地的）
- 再对A中所有元素按照个十数大小进行排序（原地的）
- 一直到最后按照A中所有元素的最高位的数字大小进行排序（原地的）
复杂度
时间复杂度
O(d(n+k))，其中d位数字的最大位宽(即这里都是d位数的整数），k为每个位数上数字取值（这里取0，1，2，3，...9）
原地排序
注意
这里尤其要重点强调，用于对指定位上的数字进行排序时，必须要满足稳定性。
快速排序就是非稳定的用小于比较的插入排序是稳定的
用小于等于比较的插入排序是不稳定的
这里必须对整数才能采取基数排序。由static_assert(...,...)确保
实现
- num
- 待抽取数字的正整数
- n
- 指定的位数（0表示个位，1表示十位，...）
|
1 2 3 4 5 6 7 |
template<typename T> T digi_on_N(T num,std::size_t n) { //必须针对整数才能取指定位数上的数字 static_assert(std::is_integral<T>::value,"T must be integer!"); return num/(T)std::pow(10,n)-num/(T)std::pow(10,n+1)*10; } |
- begin
- 待排序序列的起始迭代器（也可以是指向数组中某元素的指针）
- end
- 待排序序列的终止迭代器（也可以是指向数组中某元素的指针）
- radix_width
- 待排序元素（必须是整数）的最大位宽，必须非0（由assert(radix_width!=0)确保）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
template<typename Iterator> void radix_sort(const Iterator begin,const Iterator end,std::size_t radix_width) { typedef typename std::iterator_traits<Iterator>::value_type T; assert(radix_width != 0);//保证位数有效，0位数是无效的 //保证是针对整数进行基数排序 static_assert(std::is_integral<T>::value,"sequence to be sorted must be integer!")； auto size = std::distance(begin,end); if (size <= 1) return; for (std::size_t i = 0;i < radix_width;i++)//从0到radixwidth-1的位数排序 { //用<才是稳定排序，否则不稳定。不能用快速排序，因为不稳定 auto compare = [i](T little,T big){return digi_on_N(little,i)<digi_on_N(big,i);} insert_sort<Iterator,decltype(compare)>(begin,end,compare); } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 排序_堆排序05/08
- ♥ 排序_桶排序05/09
- ♥ BFS和DFS06/29
- ♥ 匹配_KMP模式匹配算法：二10/09
- ♥ 数据结构_最小优先级队列10/10
- ♥ 排序_计数排序05/08
热评文章
- 查找_顺序查找 0
- 算法特点、哈希表 0
- 数据结构_二叉树节点 0
- 排序_桶排序 0
- BFS和DFS 0
- 匹配_Rabin_karp匹配算法 0