解密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;
}

，并用于

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

其中temp是上面的字符数组，lineCount是数组中的字符数。通过测试验证了阵列的完整性和大小。

任何帮助都是非常感谢的。

Answer 1

char * const *是指向字符指针的指针。您只需要一个指向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！

只需创建一个int256表，并迭代数组以记录每个字符的计数：

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)。