基数排序的变种：对二进制字符串进行排序（Bitwise Radix Sort）

题目描述

我们考虑一个特殊场景：给定一个由等长的二进制字符串（例如 "1010", "0011", "1100"）组成的数组，要求在不将这些二进制字符串转换为整数的情况下，直接按照它们的二进制值（即按数值大小）进行升序排序。字符串长度固定为 L 位，数组中元素个数为 n。

例如：
输入：["1010", "0011", "1100", "0001", "1111"] (L=4)
正确排序后应为（按二进制数值从小到大）：
["0001", "0011", "1010", "1100", "1111"] （对应十进制：1, 3, 10, 12, 15）

常规的字符串字典序排序（std::sort 或直接比较字符串）无法得到数值顺序，因为字典序比较的是字符的 ASCII 码顺序。因此，我们需要设计一种基于二进制位值的排序算法。

解题过程

1. 核心思路

常规的基数排序（Radix Sort）是从最低有效位（LSB）开始，根据每一位的数值（0或1）将元素分配到两个桶中（“0”桶和“1”桶），然后按桶的顺序（先0后1）收集起来，接着对下一位（更高位）重复这个过程，直到处理完最高有效位（MSB）。对于二进制字符串，每一位只有两种可能，这非常适合使用基数排序。由于二进制位的值只有0和1，我们可以简化分配过程，实现一种高效的位基排序（Bitwise Radix Sort）。

2. 算法步骤详解

假设所有二进制字符串长度固定为 L，存储在数组 arr 中，共有 n 个字符串。

步骤1：确定排序方向
因为我们要按数值大小排序，所以应该从最高有效位（MSB）开始处理，还是从最低有效位（LSB）开始？

• 在常规的整数基数排序中，我们通常从 LSB 开始，这样能保证低位被优先排序，高位在后。
• 但对于二进制字符串，如果我们从 LSB 开始，最终得到的是按二进制数值从小到大的顺序吗？不是！因为最终高位权重最大，必须先排高位。但标准基数排序（LSD - Least Significant Digit first）确实是从低位开始，为什么可行？因为经过多轮排序后，稳定排序保证了高位的优先级。换句话说，如果我们从 LSB 开始进行稳定的分配和收集，经过 L 轮后，高位的影响最终会覆盖低位，从而实现正确排序。
  结论：我们可以选择从 LSB 开始（LSD 基数排序），但必须确保每轮排序是稳定的。也可以选择从 MSB 开始（MSD 基数排序），但 MSD 通常需要递归或额外的空间来管理子桶。为了简单起见，我们采用 LSD 方式（从最右位开始），因为二进制位只有两个可能值，实现简单且稳定。

步骤2：稳定分配策略
由于每轮只根据一个位（0或1）来分配，且需要稳定排序，我们可以采用“计数排序”的思路：

1. 统计当前位（第 i 位）上值为0的元素个数 count0 和值为1的元素个数 count1。
2. 准备一个临时数组 output（大小为 n），用于存放本轮排序后的结果。
3. 遍历原数组 arr，根据当前位的值将元素放入 output 的合适位置。为了保持稳定性，我们需要知道每个值（0和1）的起始位置。
   • 设 count0 的累积计数可以帮助我们定位。我们可以先用一个计数数组 count[2] = {0, 0} 统计频率，然后计算 count[0] 和 count[1] 的起始索引（通常 count[0] 的起始索引为0，count[1] 的起始索引为 count[0]）。
   • 但更常见且高效的方法是：使用一个 pos 数组记录每个值的起始位置。pos[0] = 0，pos[1] = count[0]。然后遍历原数组，将元素根据当前位的值放入 output[pos[bit]]，并递增 pos[bit]。

步骤3：迭代所有位
从最右边的位（索引 L-1）开始，向左处理直到最左边的位（索引 0）。每轮处理一位，并将 output 复制回 arr（或交换指针），作为下一轮的输入。

步骤4：边界情况与优化

• 所有字符串等长，所以不需要处理长度不等的情况。
• 如果字符串以字符形式存储（如 "1010"），需要访问每个字符串的第 i 个字符，并转换为数字（0或1）。
• 由于二进制位只有两个值，分配过程可以进一步优化，不需要使用完整的计数排序，可以使用“双指针分区”类似的方法，但为了稳定性，仍需小心。

3. 示例演示

以输入 ["1010", "0011", "1100", "0001", "1111"] 为例，L=4，n=5。

第1轮：处理最低位（第3位，从0开始）
当前位值（最右边位）：

• "1010" -> 0
• "0011" -> 1
• "1100" -> 0
• "0001" -> 1
• "1111" -> 1
  统计：count0 = 2 ("1010", "1100")，count1 = 3 ("0011", "0001", "1111")。
  分配并保持稳定性：
  pos[0] = 0，pos[1] = 2。
  遍历原数组：

1. "1010" (bit=0) -> output[0] = "1010"; pos[0]=1
2. "0011" (bit=1) -> output[2] = "0011"; pos[1]=3
3. "1100" (bit=0) -> output[1] = "1100"; pos[0]=2
4. "0001" (bit=1) -> output[3] = "0001"; pos[1]=4
5. "1111" (bit=1) -> output[4] = "1111"; pos[1]=5
   output = ["1010", "1100", "0011", "0001", "1111"]
   复制回 arr。

第2轮：处理第2位（右数第二位）
arr 当前 = ["1010", "1100", "0011", "0001", "1111"]
第2位值：

• "1010" -> 1
• "1100" -> 0
• "0011" -> 1
• "0001" -> 0
• "1111" -> 1
  统计：count0 = 2 ("1100", "0001")，count1 = 3 ("1010", "0011", "1111")。
  分配：
  pos[0] = 0, pos[1] = 2。
  遍历 arr：

1. "1010" (bit=1) -> output[2] = "1010"; pos[1]=3
2. "1100" (bit=0) -> output[0] = "1100"; pos[0]=1
3. "0011" (bit=1) -> output[3] = "0011"; pos[1]=4
4. "0001" (bit=0) -> output[1] = "0001"; pos[0]=2
5. "1111" (bit=1) -> output[4] = "1111"; pos[1]=5
   output = ["1100", "0001", "1010", "0011", "1111"]
   复制回 arr。

第3轮：处理第1位（右数第三位）
arr 当前 = ["1100", "0001", "1010", "0011", "1111"]
第1位值：

• "1100" -> 0 (注意：从左数第二位，索引1)
• "0001" -> 0
• "1010" -> 0
• "0011" -> 0
• "1111" -> 1
  统计：count0 = 4, count1 = 1。
  分配：
  pos[0] = 0, pos[1] = 4。
  遍历 arr：

1. "1100" (bit=0) -> output[0] = "1100"; pos[0]=1
2. "0001" (bit=0) -> output[1] = "0001"; pos[0]=2
3. "1010" (bit=0) -> output[2] = "1010"; pos[0]=3
4. "0011" (bit=0) -> output[3] = "0011"; pos[0]=4
5. "1111" (bit=1) -> output[4] = "1111"; pos[1]=5
   output = ["1100", "0001", "1010", "0011", "1111"]（本轮未改变顺序）
   复制回 arr。

第4轮：处理最高位（第0位，最左位）
arr 当前 = ["1100", "0001", "1010", "0011", "1111"]
最高位值：

• "1100" -> 1
• "0001" -> 0
• "1010" -> 1
• "0011" -> 0
• "1111" -> 1
  统计：count0 = 2 ("0001", "0011")，count1 = 3 ("1100", "1010", "1111")。
  分配：
  pos[0] = 0, pos[1] = 2。
  遍历 arr：

1. "1100" (bit=1) -> output[2] = "1100"; pos[1]=3
2. "0001" (bit=0) -> output[0] = "0001"; pos[0]=1
3. "1010" (bit=1) -> output[3] = "1010"; pos[1]=4
4. "0011" (bit=0) -> output[1] = "0011"; pos[0]=2
5. "1111" (bit=1) -> output[4] = "1111"; pos[1]=5
   output = ["0001", "0011", "1100", "1010", "1111"]？等等，检查顺序：我们希望 "1010"（10）在 "1100"（12）之前吗？是的，因为最高位相同（都是1），所以看后面位，但后面位在之前轮次已排好。由于 LSD 基数排序是稳定排序，经过前几轮后，对于最高位相同的元素，它们的相对顺序已经是按低位排序好的。这里 "1010" 和 "1100" 在之前的轮次中，"1010" 的较低位组合（010）小于 "1100" 的较低位组合（100），所以 "1010" 应该排在 "1100" 前面。
   但我们现在的 output 中 "1100" 在 "1010" 前面？这是因为我们在遍历原数组 arr 时，原数组中 "1100" 在 "1010" 前面，且它们最高位都是1，所以会按原顺序放入 output 的 bit=1 区域，而原顺序中 "1100" 在 "1010" 前面，因此最终 "1100" 在 output 中仍然在 "1010" 前面。但这正确吗？我们需要检查前一轮（第3轮）结束时 arr 的顺序，当时 arr = ["1100", "0001", "1010", "0011", "1111"]，其中 "1100" 和 "1010" 的相对顺序是：第3位（最高位？不，第3轮处理的是第1位）都是0，且它们在 arr 中的相对顺序是 "1100" 在前。由于稳定排序，这个相对顺序会保留到最高位处理。但最终按数值排序时，"1010"（10）应小于 "1100"（12），所以 "1010" 应该在 "1100" 前面。说明我们的排序还未完成？我们检查一下：实际上，LSD 基数排序要求从最低位开始，但我们的位索引顺序是从最右（最低位）到最左（最高位）。我们已经处理了所有4位，应该得到最终排序。让我们验证最终 output 的数值：
   "0001"=1, "0011"=3, "1100"=12, "1010"=10, "1111"=15。可见顺序不对（12 在 10 前面）。这说明我们上面的分配过程可能出了错，或者稳定排序的逻辑未正确实现。

让我们重新检查整个过程，确保稳定排序的实现正确。

4. 修正稳定分配的实现

常见且正确的稳定分配方法是使用计数排序的稳定版本：

1. 统计频率 count[0] 和 count[1]。
2. 计算前缀和（即起始位置）：pos[0] = 0; pos[1] = count[0]。
3. 遍历原数组 arr，将每个元素根据当前位 bit 放入 output[pos[bit]]，然后 pos[bit]++。
4. 复制 output 到 arr。

按照这个方法重新执行例子，确保每一步正确。

第1轮（位3）：
count = [2,3]; pos = [0,2]
arr[0]="1010"(0) -> output[0]="1010"; pos[0]=1
arr[1]="0011"(1) -> output[2]="0011"; pos[1]=3
arr[2]="1100"(0) -> output[1]="1100"; pos[0]=2
arr[3]="0001"(1) -> output[3]="0001"; pos[1]=4
arr[4]="1111"(1) -> output[4]="1111"; pos[1]=5
output = ["1010","1100","0011","0001","1111"] 正确。

第2轮（位2）：
arr = output from prev
count: 位2值： "1010"->1, "1100"->0, "0011"->1, "0001"->0, "1111"->1 => count=[2,3]; pos=[0,2]
遍历 arr:
arr[0]="1010"(1) -> output[2]="1010"; pos[1]=3
arr[1]="1100"(0) -> output[0]="1100"; pos[0]=1
arr[2]="0011"(1) -> output[3]="0011"; pos[1]=4
arr[3]="0001"(0) -> output[1]="0001"; pos[0]=2
arr[4]="1111"(1) -> output[4]="1111"; pos[1]=5
output = ["1100","0001","1010","0011","1111"]

第3轮（位1）：
arr = ["1100","0001","1010","0011","1111"]
位1值： "1100"->0, "0001"->0, "1010"->0, "0011"->0, "1111"->1 => count=[4,1]; pos=[0,4]
遍历 arr:
arr[0]="1100"(0) -> output[0]="1100"; pos[0]=1
arr[1]="0001"(0) -> output[1]="0001"; pos[0]=2
arr[2]="1010"(0) -> output[2]="1010"; pos[0]=3
arr[3]="0011"(0) -> output[3]="0011"; pos[0]=4
arr[4]="1111"(1) -> output[4]="1111"; pos[1]=5
output = ["1100","0001","1010","0011","1111"] (不变)

第4轮（位0，最高位）：
arr = ["1100","0001","1010","0011","1111"]
位0值： "1100"->1, "0001"->0, "1010"->1, "0011"->0, "1111"->1 => count=[2,3]; pos=[0,2]
遍历 arr:
arr[0]="1100"(1) -> output[2]="1100"; pos[1]=3
arr[1]="0001"(0) -> output[0]="0001"; pos[0]=1
arr[2]="1010"(1) -> output[3]="1010"; pos[1]=4
arr[3]="0011"(0) -> output[1]="0011"; pos[0]=2
arr[4]="1111"(1) -> output[4]="1111"; pos[1]=5
output = ["0001","0011","1100","1010","1111"]？仍然不对（"1100"在"1010"前）。

问题出在哪儿？注意：LSD 基数排序要求从最低位开始到最高位，每一轮必须是稳定排序。我们检查最后一轮：在最后一轮（最高位）处理前，arr 中元素的顺序是前一轮（位1）排序后的结果。在 arr 中，"1100" 和 "1010" 的当前顺序是 "1100" 在 "1010" 前面。当最高位相同时（都是1），稳定排序会保持这个相对顺序，所以最终 "1100" 仍在 "1010" 前面。但根据数值比较，"1010"（10）应该排在 "1100"（12）前面。这说明在前一轮（位1）排序后，这个相对顺序已经错了。为什么位1排序后，"1100" 在 "1010" 前面？让我们检查位1排序前的数组（第2轮后）是 ["1100","0001","1010","0011","1111"]，其中 "1100" 和 "1010" 的位1值都是0，所以稳定排序保持它们原来的相对顺序（"1100" 在 "1010" 前面）。但为什么位2排序后，"1100" 在 "1010" 前面？检查位2排序前（第1轮后）是 ["1010","1100","0011","0001","1111"]，其中 "1010" 和 "1100" 的位2值分别为1和0，所以排序后 "1100"（位2=0）应该在 "1010"（位2=1）前面，这是正确的，因为位2是次高位，权重高于更低位的位1和位0。实际上，对于二进制数值比较，高位权重更大，所以应该先排高位（MSD）才直观，但 LSD 基数排序通过从低位到高位多轮稳定排序，最终高位会起决定性作用。然而这里出现了错误，是因为我们的位索引顺序搞错了。

我们应该从最低有效位（LSB）开始，但最低有效位是二进制字符串的最右边一位，即索引 L-1。我们之前从索引 L-1 开始向左到 0，这是正确的。但是，对于二进制数值，最高位是索引 0（最左），最低位是索引 L-1（最右）。LSD 基数排序从最低位开始，也就是从索引 L-1 开始，然后向索引 0 移动。我们正是这样做的。那么为什么结果不对？让我们手动计算正确排序过程：

正确排序顺序应为（按数值升序）：

1. 0001 (1)
2. 0011 (3)
3. 1010 (10)
4. 1100 (12)
5. 1111 (15)

从最低位（位3）开始排序：
原始数组：["1010", "0011", "1100", "0001", "1111"]
按位3（最低位）稳定排序后：所有位3=0 的排在位3=1 的前面，且保持原相对顺序。
位3=0: "1010", "1100"
位3=1: "0011", "0001", "1111"
结果：["1010", "1100", "0011", "0001", "1111"]（与第1轮一致）

按位2排序（次低位）：
当前数组：["1010", "1100", "0011", "0001", "1111"]
位2值：
"1010"->1, "1100"->0, "0011"->1, "0001"->0, "1111"->1
稳定排序：位2=0 的排在前面，位2=1 的排在后面，且各自保持内部相对顺序。
位2=0: "1100", "0001" （注意原顺序中 "1100" 在 "0001" 前）
位2=1: "1010", "0011", "1111" （原顺序 "1010","0011","1111"）
结果：["1100", "0001", "1010", "0011", "1111"]（与第2轮一致）

按位1排序（第三低位）：
当前数组：["1100", "0001", "1010", "0011", "1111"]
位1值：
"1100"->0, "0001"->0, "1010"->0, "0011"->0, "1111"->1
稳定排序后：位1=0 的在前，位1=1 的在后。
位1=0: "1100", "0001", "1010", "0011" （保持原序）
位1=1: "1111"
结果：["1100", "0001", "1010", "0011", "1111"]（不变）

按位0排序（最高位）：
当前数组：["1100", "0001", "1010", "0011", "1111"]
位0值：
"1100"->1, "0001"->0, "1010"->1, "0011"->0, "1111"->1
稳定排序：位0=0 的在前，位0=1 的在后。
位0=0: "0001", "0011" （原序 "0001","0011"）
位0=1: "1100", "1010", "1111" （原序 "1100","1010","1111"）
最终结果：["0001", "0011", "1100", "1010", "1111"]

这里 "1100" 仍然在 "1010" 前面，但数值上 "1100"（12）> "1010"（10），所以顺序错误。这说明 LSD 基数排序在处理二进制字符串时，如果从最低位开始，最终得到的是按无符号二进制整数从小到大排序吗？让我们验证：最终数组对应的十进制是 [1,3,12,10,15]，确实不是完全升序。问题在于 LSD 基数排序要求位权重从低到高，而我们的位索引 0 是最高权重（MSB），L-1 是最低权重（LSB）。但我们处理顺序是从 L-1 到 0，这是从低权重到高权重，是正确的。为什么结果不对？因为对于相同的高位（位0=1）的元素 "1100" 和 "1010"，它们的低位顺序在上一轮排序后已经被决定了，而上一轮（位1）排序后，它们的顺序是 "1100" 在 "1010" 前面。但是，在二进制数值比较中，当最高位相同时，我们应该比较次高位（位1），而位1上 "1100" 是 1，"1010" 是 0，所以 "1010" 应该排在 "1100" 前面。这意味着在上一轮（位1）排序时，我们应该把位1=0 的排在位1=1 的前面，但实际排序中，由于位1 的值 "1100" 是 1，"1010" 是 0，所以 "1010" 应该排在 "1100" 前面，但我们的排序结果却是 "1100" 在 "1010" 前面。为什么？因为我们的排序是稳定排序，而在位1排序时，输入数组中的顺序是 "1100" 在 "1010" 前面，且它们的位1值不同（"1100" 的位1=1，"1010" 的位1=0），所以稳定排序会按位1值分组，位1=0 的组在前，位1=1 的组在后。那么 "1010" 应该被分到位1=0 组，"1100" 到位1=1 组，所以 "1010" 应该在 "1100" 前面。但我们实际执行时，位1排序后的结果是 ["1100", "0001", "1010", "0011", "1111"]，其中 "1100" 在 "1010" 前面，这说明我们的位1排序没有正确分组。让我们检查位1排序的具体操作：

位1排序输入：["1100", "0001", "1010", "0011", "1111"]（这是位2排序后的结果）
位1值：
索引0: "1100" -> 字符索引1 是 '1'? 注意：字符串索引从0开始，位0是最高位。对于 "1100"，位0='1', 位1='1', 位2='0', 位3='0'。所以位1值是 '1'。
索引1: "0001" -> 位1='0'
索引2: "1010" -> 位1='0'
索引3: "0011" -> 位1='0'
索引4: "1111" -> 位1='1'
所以位1值数组：[1,0,0,0,1]
count = [3,2]（位1=0的有3个，位1=1的有2个）
pos = [0,3]
遍历输入数组：

1. "1100" (bit=1) -> output[3]="1100"; pos[1]=4
2. "0001" (bit=0) -> output[0]="0001"; pos[0]=1
3. "1010" (bit=0) -> output[1]="1010"; pos[0]=2
4. "0011" (bit=0) -> output[2]="0011"; pos[0]=3
5. "1111" (bit=1) -> output[4]="1111"; pos[1]=5
   output = ["0001", "1010", "0011", "1100", "1111"]
   这才是正确的位1排序结果！而我们之前在第3轮计算时错误地将位1值判断错了（之前误以为 "1100" 的位1是0，实际上是1）。更正后，位1排序后数组变为 ["0001", "1010", "0011", "1100", "1111"]。

继续位0排序（最高位）：
输入：["0001", "1010", "0011", "1100", "1111"]
位0值：
"0001"->0, "1010"->1, "0011"->0, "1100"->1, "1111"->1
count = [2,3]; pos=[0,2]
遍历：

1. "0001"(0) -> output[0]="0001"; pos[0]=1
2. "1010"(1) -> output[2]="1010"; pos[1]=3
3. "0011"(0) -> output[1]="0011"; pos[0]=2
4. "1100"(1) -> output[3]="1100"; pos[1]=4
5. "1111"(1) -> output[4]="1111"; pos[1]=5
   output = ["0001", "0011", "1010", "1100", "1111"]
   这正是我们期望的排序结果（1,3,10,12,15）！

因此，之前错误是由于在手动计算时取错了某一位的值。在实现时，必须确保正确提取每一位。

5. 算法实现（伪代码）

function bitwiseRadixSort(arr, L):
    n = arr.length
    output = new array of size n
    for bit from L-1 down to 0:   // 从最低位到最高位
        count = [0, 0]
        // 统计当前位值为0和1的个数
        for i from 0 to n-1:
            bitVal = arr[i][bit] - '0'  // 获取二进制字符 '0' 或 '1' 的数值
            count[bitVal]++
        // 计算起始位置
        pos = [0, count[0]]
        // 稳定分配
        for i from 0 to n-1:
            bitVal = arr[i][bit] - '0'
            output[pos[bitVal]] = arr[i]
            pos[bitVal]++
        // 复制回原数组
        arr = output  // 或交换指针
    return arr

6. 时间复杂度与空间复杂度

• 时间复杂度：O(L * n)，因为每轮遍历数组两次（统计和分配），共 L 轮。
• 空间复杂度：O(n)，用于临时数组 output。
  由于二进制位只有两种取值，该算法非常高效，尤其适用于长度固定的二进制字符串排序。

7. 拓展思考

• 如果二进制字符串长度不等，可以在短字符串前补0到相同长度，然后再排序。
• 该算法可以推广到任意进制的字符串排序（例如十六进制字符串），只需将 count 数组大小改为进制数即可。
• 对于整数数组，可以直接对整数的二进制位进行操作，无需转换成字符串。

通过以上步骤，我们完成了对二进制字符串按数值排序的算法设计与分析。核心是利用 LSD 基数排序的稳定性，从最低位到最高位逐位排序，最终得到数值顺序。