适配count[27]的LSD基数排序字符串排序异常，求解决方案

核心错误定位 #

你的代码里逆序遍历填充B数组时，else分支的count索引计算错误，这是导致排序后字符串重复的关键原因：

原代码中else分支：

strcpy(B[count[A[i][d] - 'a' + 1] - 1], A[i]);
count[A[i][d]]--;  // 这里索引完全错了！

这里count[A[i][d]]用的是字符的原始ASCII值（比如'a'对应97），但你的count数组只有27个元素（索引0-26），这会直接导致数组越界访问，破坏count数组的计数逻辑，最终排序时出现重复或顺序混乱。

修正方案 #

把else分支里的count[A[i][d]]--改成和前面一致的索引计算方式：count[A[i][d] - 'a' + 1]--，这样才能正确维护count数组的计数位置。

修正后的else分支代码：

else {
    int idx = A[i][d] - 'a' + 1;
    strcpy(B[count[idx] - 1], A[i]);
    count[idx]--;
}

额外优化建议 #

• 用' '代替魔法数字32，代码可读性更强：if(A[i][d] == ' ')
• 确保传入的k值固定为27，对应count数组的大小（0对应空格，1-26对应a-z），如果k不是27也会导致计数逻辑出错
• 注意字符串终止符：如果max是字符串的最大长度，要确保每个字符串都以\0结尾，避免strcpy操作越界

完整修正后的代码 #

#define MAX 15
void foo(char** A, int n, int k, int max) {
  int i, d;
  char** B = (char**)malloc(sizeof(char*) * n);

  for(i = 0; i < n; i++)
    B[i] = (char*)malloc(sizeof(char) * max);

  for (d = max - 1; d >= 0; d--) {
    int* count = (int*)malloc(sizeof(int) * k);
    
    for(i = 0; i < k; i++)
      count[i] = 0;

    for (i = 0; i < n; i++) {
      if(A[i][d] == ' ') 
          count[0]++;
      else 
          count[A[i][d] - 'a' + 1]++;
    }

    for (i = 1; i < k; i++)
      count[i] += count[i - 1];
    
    for (i = n - 1; i >= 0; i--) {
      if(A[i][d] == ' ') {
        strcpy(B[count[0] - 1], A[i]);
        count[0]--;
      }
      else {
        int idx = A[i][d] - 'a' + 1;
        strcpy(B[count[idx] - 1], A[i]);
        count[idx]--;
     }
    }

    for (i = 0; i < n; i++)
      strcpy(A[i], B[i]);

    free(count);
  }

  for(i = 0; i < n; i++) free(B[i]);
  free(B);
}

内容的提问来源于stack exchange，提问作者megarubber