基数排序 | Jimmy Huang’s Blog²

type

status

基数排序（也叫桶排序）是一种很特别的排序方法，它不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。

基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序

最低位用的比较多

是根据键值的每位数字来分配桶的

中r为所采取的基数，而n为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

以低位（LSD）为例从低位到高位的顺序进行排序例如最高是百位的话，先从个位开始排序，然后是十位，最后是百位，如动图所示

稳定

顺序存储和链式存储

c++

最大的难点应该就是这两个循环了

如何理解这两个循环，决定了如何理解算法如何确定出每个元素在tmp数组中的下标表示以int arr[] = {13, 14, 8, 100, 25, 75, 9, 64, 12};为例子第一个循环的作用

目的：让更改后的buckets[i]的值，是在数据在tmp[]中的位置

第二个循环的作用

将桶内记录依次放到tmp数组中

Jimmy Huang