【图解数据结构】 一组动画彻底理解基数排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 —–《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

基数排序

基数排序 (Radix Sort) 是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。

基数排序法会使用到桶 (Bucket),顾名思义,通过将要比较的位(个位、十位、百位…),将要排序的元素分配至 0~9 个桶中,借以达到排序的作用,在某些时候,基数排序法的效率高于其它的比较性排序法。

算法步骤

  1. 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零

  2. 从最低位开始,依次进行一次排序

  3. 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

算法演示

动画演示GIF加载有点慢,请稍等片刻^_^
【图解数据结构】 一组动画彻底理解基数排序

排序动画过程解释

  1. 基数排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)

  2. 在本例中使用的是 LSD

  3. 首先创建编号 0 , 1 ,2 ,3 ,4 ,5 , 6 ,7 ,8 ,9  10 个桶

  4. 遍历整个数列,查看数字的个位数,按照先后顺序存放在对应编号的桶中

  5. 比如 321 个位数 为 1 ,存放在编号 1 桶中

  6. 数字 1 个位数 为  1 ,存放在编号  1  桶中,同时存放在 321 上面

  7. 遍历完整个数列的个位数,将数字存放在桶中后,按照编号顺序取出数字,先放入桶中的数字先取出

  8. 然后依次遍历整个数列的十位数,按照上述个位数的操作整理数列

  9. 依次遍历整个数列的百位数,按照上述个位数的操作整理数列

  10. 这样就完成了 基数排序

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

Java代码实现

【图解数据结构】 一组动画彻底理解基数排序

JavaScript代码实现

【图解数据结构】 一组动画彻底理解基数排序

大家都在看

┣ 【图解数据结构】一组动画彻底理解冒泡排序

┣ 【图解数据结构】一组动画彻底理解归并排序

┣ 【图解数据结构】一组动画彻底理解选择排序

┣ 【图解数据结构】一组动画彻底理解快速排序

┣ 【图解数据结构】一组动画彻底理解插入排序

┣ 【图解数据结构】一组动画彻底理解希尔排序

┣ 【图解数据结构】一组动画彻底理解堆排序

┣ 【图解数据结构】一组动画彻底理解计数排序


【图解数据结构】 一组动画彻底理解基数排序
【图解数据结构】 一组动画彻底理解基数排序
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 【图解数据结构】 一组动画彻底理解基数排序

我还会在以下平台发布内容

GitHub 哔哩哔哩