基数排序最高位优先为什么是错的（基数排序和桶排序的区别）
前言
随着算法竞赛的发展，它对算法解决问题的能力要求更高，同时要求选手不断进行创新优化以及突破，并且要求算法具有一定的”通用性“，不能适应应用环境的算法终将渐渐淡出视野。因此研究一些并不是常用的算法也是比较重要的，特别是该算法在算法竞赛中体现出了实用性以及对陈旧的解法的突破。一个比较基础的算法——基数排序便是如此，本文便是在介绍基数排序的基础上尝试加以优化的同时提高”通用性“。
引入
我们知道“基于交换的排序算法时间复杂度下限是”（可以简单地理解为给定序列的排列方式有种，然后我们每次进行一次交换最多可以排除掉一半的序列，最后复杂度相当于（斯特林公式可求））。 但是现实中算法总会有常数，而且快速排序会被卡（C++对sort的优化还可以，例如根据数据特征判断不同时候的方法等等），一般情况下stable_sort采用的是归并排序和插入排序（详见STL源码），其实效率有时还会高一些。
桶排序
但是如果希望一个的排序怎么办？我们学习过一个传统的桶排序，这里稍微介绍一下桶排序，时间复杂度为。
桶排序的原理是按照值把待排序的分类并且存入容器中，然后顺序扫描容器，就可以按照顺序得到所有元素，例如
实现方法
这里直接以template作为参数进行32位排序，这个参数接受不高于32位的类型。a为待排序数组，b为临时数组 现在看看代码如何写。
1、首先开四个数组作为4个关键字的桶（基数为 2^828 ）
2、把元素用二进制运算拆开，放入桶内
3、桶子进行桶排序，利用上一次排序的结果交替利用数组进行下一次排序
注意结构体排序的待排序关键字应该定义在结构体的前面（和内存有关），不建议使用union。同时在以前所有r数组开的都是0xff的大小,但是后来考虑到实际使用的时候不同的机子或不同的时间下有不同的内存情况,所以后来把数组扩大了1和《算法导论》对基于交换的排序算法的下限的分析。
所有算法都有其存在的意义与价值。
本文发布于洛谷日报，特约作者：Creeper_LKF
原文地址：https://www.luogu.org/blog/CreeperLKF/Radix-Sort返回搜狐，查看更多