排序算法之：循环不变式在基数排序中的正确性证明

题目描述
基数排序（Radix Sort）是一种非比较型整数排序算法，它通过逐位处理数字的各个位数（从最低有效位到最高有效位，或反之）来实现排序。本题要求你理解基数排序的工作原理，并运用循环不变式（Loop Invariant）来严谨证明该算法的正确性。证明过程需确保在每一轮按位处理（如个位、十位、百位）后，数组都能维持一个关键性质，最终保证整体有序。

解题过程循序渐进讲解

1. 基数排序基础回顾

   • 基数排序假设输入数组由固定位数的整数组成（若位数不同，可通过前导零补齐）。
   • 算法按位排序：从最低位（LSB）到最高位（MSB），或反向（MSB到LSB）。通常使用稳定排序算法（如计数排序）对每一位进行排序。
   • 示例：数组 [170, 45, 75, 90, 2, 802, 24]，从最低位开始排序：
     • 按个位排序后：[170, 90, 802, 2, 24, 45, 75]
     • 按十位排序后：[802, 2, 24, 45, 170, 75, 90]
     • 按百位排序后：[2, 24, 45, 75, 90, 170, 802]（最终有序）。

2. 定义循环不变式

   • 循环不变式是算法中在每次循环迭代前后均成立的条件。对于基数排序，我们关注第k轮处理后的数组状态。
   • 设数组有d位数字（从第1位到第d位，第1位为最低位）。循环不变式定义为：
     “在第k轮排序后（即处理完第1位到第k位），数组中所有元素按其最低k位构成的数值从小到大有序。”
     • 例如：k=1时，数组按个位有序；k=2时，数组按“十位+个位”组成的两位数有序。

3. 证明循环不变式的正确性

   • 初始化（k=0）：
     • 尚未处理任何位时，数组可能无序，但“按最低0位有序”可视为空条件，因此不变式平凡成立。
   • 保持（k轮 → k+1轮）：
     • 假设第k轮后不变式成立（数组按最低k位有序）。
     • 第k+1轮对第k+1位（更高一位）进行稳定排序（如计数排序）。
     • 关键点：稳定排序会保持相同高位数下低位数原有的顺序。例如，若两个元素第k+1位相同，它们的顺序由低k位决定，而低k位已在上一步有序，因此稳定排序不会打乱其相对顺序。
     • 因此，排序后数组按最低k+1位有序：先按第k+1位分组，组内按低k位有序，整体有序。
   • 终止（k=d）：
     • 处理完所有d位后，数组按完整的d位数值有序，即整体有序。

4. 边界与稳定性分析

   • 若位数不足d，可假设高位为0，不影响证明。
   • 稳定性是证明的核心：若不稳定，低k位的顺序可能被破坏，导致不变式失效。

总结
通过循环不变式，我们严格证明了基数排序的每一步都维护了“部分有序”性质，最终扩展到全局有序。此方法突出了稳定排序在基数排序中的关键作用，并提供了分析复杂排序算法的通用框架。