基数排序

排序算法

基数排序是一种非比较型的排序算法,通过逐位比较元素的每一位(从最低位到最高位)来实现排序。

时间复杂度:最佳 O(n * k) | 平均 O(n * k) | 最差 O(n * k)
空间复杂度:O(n + k)
稳定性:稳定

应用场景/前提条件

  • 适用于整数排序
  • 非比较型排序
  • k为最大整数位数

算法讲解

介绍

基数排序(Radix Sort)是一种非比较型的排序算法,核心思想是按照数位来排序,从最低有效位(Least Significant Digit, LSD)或最高有效位(Most Significant Digit, MSD)开始,依次对每个位置的数字进行排序。基数排序特别适合用于整数或定长字符串的排序,时间复杂度是 O(n×k),其中 n 是待排序数组的长度,k 是数据的最大位数。

基数排序不会直接比较元素之间的大小,通过分配和收集过程实现排序,在一些特定场景下性能优于比较排序算法。

算法步骤

  1. 找出待排序数组中的最大值,确定最大位数
  2. 从最低位开始,对每一位上的数字进行计数排序(或桶排序)
  3. 按照当前位的数字大小将元素重新排列
  4. 对下一个更高位重复步骤2和3,直到处理完所有位

注意:每一轮只看当前这一位上的数字来分桶,不看其他位。比如按十位分桶时,436 和 839 的十位都是 3,放进同一个桶;355、457、657 的十位都是 5,放进另一个桶。同一个桶内的元素保持上一轮的先后顺序(稳定性),这正是低位排序结果能够被保留下来的原因。

核心特性

  • 非比较排序:不通过比较元素大小进行排序
  • 稳定排序:相等元素的相对位置在排序后不会改变

...