基数排序(Radix sort) gaunthan Posted on Aug 7 2016 ? Sorting ? ? Algorithm ? ## 思想 基数排序（radix sort）是一种用在卡片排序机上的算法，因此有时也称为**卡式排序**（card sort）。基数排序分为**LSD**（Least significant digital）和**MSD**（Most significant digital）。LSD从低位开始排到高位，每排一位都是把各个桶合并，再按下一位排序；MSD从高位开始排到低位，排完一位后不合并桶，相同的高位划分子桶继续分配，最后再合并。 ## 操作演示 对d位数的排序需要进行d轮。下面是一个示例，它展示了由7个三位十进制数组成的列表的基础排序过程，最左边的矩形内存放的是输入数据，其余矩形表明的是经过一轮操作后的结果。正在操作的数位用红色标出：  显然，上面的排序是以LSD方式进行的。 ## 实现 ```c radixSort(A,d) for i = 1 to d use a stable sort to sort array A on digit i ``` ## References - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. 赏 Wechat Pay Alipay 数据结构：散列表 冒泡排序(Bubble sort)
