基数排序算法

2022年12月30日 · 282 字 · 2 分钟

基数排序又叫桶排序，是一种时间复杂度为$O(n)$的排序算法，但是相比于其他排序算法有$O(n)$的空间复杂度。 思路 基数排序的核心思路如下： 准备0~9的10个桶，根据数字当前比较位的值来决定放入哪个桶。如当前比较个位，则数字13应该放入索引为3的桶中；当前比较百位，则123应该放入索引为1的桶中。 当所有数字全部放入桶之后，遍历0~9这10个桶，然后依次将数字保存到待排序数组，因为桶是有序的，所以本轮放回去的数字是有序的。 当前比较的位数左移，比如本轮比较个位，下一轮应该比较百位。 重复步骤1~3。 举例 现在我们来看一个实际例子。