文章目录[x]
- 1:基数排序
- 2:算法步骤
- 3:算法演示
- 4:排序动画过程解释
基数排序
基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。
基数排序法会使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。
算法步骤
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
算法演示
动画演示GIF加载有点慢，请稍等片刻^_^
排序动画过程解释
- 基数排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)
- 在本例中使用的是 LSD
- 首先创建编号 0 ， 1 ，2 ，3 ，4 ，5 ， 6 ，7 ，8 ，9 这 10 个桶
- 遍历整个数列，查看数字的个位数，按照先后顺序存放在对应编号的桶中
- 比如 321 个位数 为 1 ，存放在编号 1 桶中
- 数字 1 个位数 为 1 ，存放在编号 1 桶中，同时存放在 321 上面
- 遍历完整个数列的个位数，将数字存放在桶中后，按照编号顺序取出数字，先放入桶中的数字先取出
- 然后依次遍历整个数列的十位数，按照上述个位数的操作整理数列
- 依次遍历整个数列的百位数，按照上述个位数的操作整理数列
- 这样就完成了 基数排序
转载自：https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484076&idx=1&sn=fb551e1eb83cd483c7a963cbc432e4bd&chksm=fa0e6d2dcd79e43bc4387b3fd89c61dcc084a4e7396c453d9194f0ae357f1cf725eabd39ebb9&scene=21#wechat_redirect