编辑“︁基数排序”︁

{{DISPLAYTITLE:基数排序}}  
'''基数排序'''（Radix Sort）是一种非比较型的整数排序算法，通过逐位分配和收集元素实现排序。其核心思想是将整数按位数切割成不同数字，然后按每个位数分别比较。基数排序适用于整数或字符串（按字典序）的排序，时间复杂度可达线性级（<math>O(nk)</math>，其中<math>n</math>为元素数量，<math>k</math>为最大位数）。

== 算法原理 ==  
基数排序分为以下步骤：  
1. '''确定最大位数'''：找到数组中最大数字的位数<math>d</math>。  
2. '''按位排序'''：从最低位（LSD，Least Significant Digit）或最高位（MSD，Most Significant Digit）开始，依次对每一位进行稳定排序（通常使用计数排序）。  
3. '''合并结果'''：每轮排序后，按当前位数重新排列数组，最终得到有序序列。

=== LSD vs MSD ===  
* '''LSD'''（最低位优先）：从右向左逐位排序，适用于位数较少的整数。  
* '''MSD'''（最高位优先）：从左向右递归排序，适用于字符串或位数差异大的数据。

== 算法步骤示例 ==  
以数组<code>[170, 45, 75, 90, 802, 24, 2, 66]</code>为例：  

1. 找到最大数802（3位数），补齐其他数字为3位：<code>[170, 045, 075, 090, 802, 024, 002, 066]</code>。  
2. 按个位、十位、百位依次排序：  

<mermaid>  
flowchart LR  
    A[原始数组] --> B[按个位排序]  
    B --> C[170, 090, 802, 002, 024, 045, 075, 066]  
    C --> D[按十位排序]  
    D --> E[802, 002, 024, 045, 066, 170, 075, 090]  
    E --> F[按百位排序]  
    F --> G[002, 024, 045, 066, 075, 090, 170, 802]  
</mermaid>  

== 代码实现 ==  
以下是Python实现的基数排序（LSD版本）：  

<syntaxhighlight lang="python">  
def radix_sort(arr):  
    # 获取最大位数  
    max_num = max(arr)  
    max_digit = len(str(max_num))  

    for digit in range(max_digit):  
        # 使用计数排序对当前位排序  
        count = [0] * 10  
        output = [0] * len(arr)  

        # 统计当前位数字出现次数  
        for num in arr:  
            current_digit = (num // (10 ** digit)) % 10  
            count[current_digit] += 1  

        # 计算累积分布  
        for i in range(1, 10):  
            count[i] += count[i - 1]  

        # 按当前位重新排列  
        for num in reversed(arr):  
            current_digit = (num // (10 ** digit)) % 10  
            output[count[current_digit] - 1] = num  
            count[current_digit] -= 1  

        arr = output.copy()  
    return arr  

# 示例  
input_arr = [170, 45, 75, 90, 802, 24, 2, 66]  
print("输入数组:", input_arr)  
sorted_arr = radix_sort(input_arr)  
print("排序结果:", sorted_arr)  
</syntaxhighlight>  

'''输出'''：  
<pre>  
输入数组: [170, 45, 75, 90, 802, 24, 2, 66]  
排序结果: [2, 24, 45, 66, 75, 90, 170, 802]  
</pre>  

== 复杂度分析 ==  
* 时间复杂度：<math>O(nk)</math>（<math>k</math>为最大位数）。  
* 空间复杂度：<math>O(n + k)</math>（辅助计数数组和输出数组）。  
* 稳定性：稳定（依赖底层计数排序的稳定性）。  

== 实际应用 ==  
1. '''卡片排序机'''：早期机械式排序设备采用类似原理。  
2. '''大数据处理'''：如Hadoop中对海量整数排序。  
3. '''字符串字典序排序'''：如电话号码或车牌号排序。  

== 优缺点 ==  
{| class="wikitable"  
|+  
! 优点 !! 缺点  
|-  
| 线性时间复杂度优于比较排序（如快速排序） || 仅适用于整数或固定格式字符串  
| 稳定排序，保持相同键值的顺序 || 空间复杂度较高  
|}  

== 扩展思考 ==  
* 如何优化基数排序对负数的处理？  
* 比较基数排序与桶排序的异同。  

{{Algorithms}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]