解读 qsort 行为

Question

我需要 qsort 的功能来运行我的程序，但到目前为止还没有完成它的工作。

我本质上是对单个字符值的数组进行排序，以便将它们分组，以便我可以迭代该数组并确定每个属性的计数。我的问题是 qsort 返回一个“已排序”数组，因为

xxxxxbxbbbxfbxfbffffbxfxbbfbbbxxfxbxxfbbbbxbfxbxfbxbsxbbbxxbbxxffxbxfxfxbxxbxxfbbbfbxbbx
bbbsxfxbxbxxbfbfxbxxbxxbfxxbxsbfxxfxfxfffxbfxffbbfffsxsfbfbxbxbbbxxsbfbfbbbbbbxxfxfxffxf
xbxxbxfxbfbxbxxbxbxxbxbbffxxbxxffxxbxfxbxffxfsfxxfxxfxxfxfxxfxxbsxxbbbxsxxbbxxxbxfxsbxxx
ffbxfxxffbxxxfxxfxxfxfxxfffbxxxbxxxfffxsbbfffffxxxbbfxsbffxbxxfxbxxfbbfsbffsfffxfxfxbbffx
bxxfxbxxfxbbbfxxbbfxxbbbsxbxfbfbbxxbbfffxxfxxbbbfxxbxxxbbxxxbfxffxxxffxfxxffbxfsxbxxxfxfx
fsbbbxxxbfxfffsfxxxfssxxxfxfxxxxbxbbbxxbxxxxxxxxxxxxxxxxxxxfbfxxffxxbxxxxxxxsxsxxxxxxxxsxb
bxxxxxfxbxxxxfxxfxxxxxbbxfffbxbsxffbbbxsfbbfffbxbfbbxxbxxbbxxbffxfxxfxfbbxxbxfxxsfxxfxxbxf
xxbxxxbxbxbbxbbffxxxxbfbfxxxxxxfxffxxxxxxxxxxxxxxxxxxxxxbxffxbxbxbbxbbxxfbxfxbxxbxxbxbxxxb
xxbxbxbfbbffffffsbbxxbffbxfxxfxbfbfffsxbxxxsxxbbbbbxxxbxxxfxxfffxxxxxxxxxxxxxfxxbxxxxxxxxx
xxbfbxxxxxxxxxxxxxxxxxxxxxxxxxxbxbxxxxxfxxbxxxxffxbxxxxffxfbfffxbxxfxbfxbxxfxbxbfxxxxxfxbx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxsbxxxxffxfxxxxxxxxxfxfxxxbffffxxxfbxbxfxxxxxxxxxxxxxxxxxxxxf
fxfxbfxxxfxxxxx

我认为问题与我的函数调用或比较方法有关。

int compare(const void *a, const void *b){
  return *(char * const *) a - *(char * const *) b;
}

and 用于其中

qsort(temp, lineCount, sizeof(char), compare);

temp 是上面的字符数组，lineCount 是数组中的字符数。阵列的完整性和尺寸均已通过测试验证。

非常感谢任何帮助。

Answer 1

char * const * 是一个指向 char 的指针。你只想要一个指向 char 的指针。

尝试：

int compare(const void *a, const void *b){
    return *(const char *) a - *(const char *) b;
}

此外，根据定义，sizeof(char) 始终等于 1。所以有些C程序员永远不会这样写出来。 （它是否使代码更易于阅读，或者只是表明您并不真正了解该语言，这是一个观点问题。我碰巧喜欢这种情况，但仅供参考。）

Answer 2

至少一开始，我只是更明确地逐行编写比较，以便于调试：

int compare(const void *a, const void *b)
{
    char* alpha = (char*)a;   // Might get const-warning on these lines, ignore for now.
    char* beta  = (char*)b;

    if (*alpha == *beta) return 0;
    if (*alpha < *beta) return -1;
    return 1;
}

这样，您可以更轻松地在调试器中观察它，添加输出行，并通常分解问题。

一旦它再次工作，您可以将其重新组合成一行紧凑的代码。

Answer 3

试试这个：

int compare(const void *a, const void *b){
  return *(const char *) a - *(const char *) b;
}

但是恕我直言，你根本不需要qsort！

只需创建一个 int[256]（或可能更少）的表并迭代该数组来记录每个字符的计数：

int res[256];
memset(res, 0, 256*sizeof(int));
int i;
for (i=0;i<lineCount;i++){
    res[tmp[i]]++;
}

这将提供 O(N) 与 qsort 的 O(NlogN)。