基数排序时如何使字符串粘在一起？

Question

我必须编写一个程序，使用基数排序对字符串（精确长度为 7 个字符）进行排序。我已经制作了一个单独对每一列进行排序的函数。我的问题是如何让整个字符串移动，而不仅仅是一个字符。看到它在 C 中应该如何工作对我来说真的是个问题。

我制作了一个数组 "char strings[3][8]" 和 "char output[3][8]" 来对 3 个字符串进行排序，每个字符串中正好有 7 个字符。例如对这些字符串进行排序：

strcpy(strings[0], "kupbars");
strcpy(strings[1], "daparba");
strcpy(strings[2], "jykaxaw");

在输出中我得到：

dakaaaa
juparbs
kypbxrw

每一列都正确排序，但字符没有粘在一起。试了很多方法3个小时都没用

我的代码如下所示：

void countingSort(char a[][8], char b[][8]) {
  int c[123];
  for (int pos = 6; pos >= 0; pos--) {
    for (int i = 0; i < 123; i++)
      c[i] = 0;
    for (int i = 0; i < 3; i++)
      c[(int)a[i][pos]]++;
    for (int i = 1; i < 123; i++)
      c[i] += c[i - 1];
    for (int i = 2; i >= 0; i--) {
      b[--c[(int)a[i][pos]]][pos] = a[i][pos];
    }
  }
}

（有限制字符串长度等的常量，因为很容易将其更改为变量 - 我只是专注于让这个程序正常工作。）

Answer 1

您可以做一个循环列表，但这有点开销。我建议你使用 memmove().

#include <string.h>

void array_move_forward(char array[3][8]) {
  for (int i = 0; i < 3; i++) {
    char tmp = array[i][6];
    memmove(array[i] + 1, array[i], 6);
    array[i][0] = tmp;
  }
}

void array_move_rewind(char array[3][8]) {
  for (int i = 0; i < 3; i++) {
    char tmp = array[i][0];
    memmove(array[i], array[i] + 1, 6);
    array[i][6] = tmp;
  }
}

另一种解决方案是自己操作字符串并使用索引，指示字符串的第一个字母。

{
  char str[7];
  int i = 0;
  ...
  int j = i;
  for (int k = 0; k < 7; k++) {
    char tmp = str[j++ % 7];
  }
}

这样你就可以用 i++ 或 i--.

旋转你的字符串

struct my_string_radix {
  char str[7];
  int begin;
}

Answer 2

尝试更改循环以移动整个字符串：

    for (int i = 2; i >= 0; i--) {
        int k = --c[(int)a[i][pos]];
        for(int j = 0; j < 8; j++) {
            b[k][j] = a[i][j];
        }
    }

基数排序时如何使字符串粘在一起？

How to make strings stick together while radix sorting?

c

arrays

string

sorting

radix-sort