为什么 qsort 最多只能对 8 个元素进行排序

Why does qsort only sorts a maximum of 8 elements

提问人:doubleSpace 提问时间:12/2/2022 最后编辑:JabberwockydoubleSpace 更新时间:12/2/2022 访问量:88

问:

我正在编写一个代码,该代码使用来自 <stdlib.h> 的 qsort。虽然我的代码对于将要排序的数组中的 8 个元素绝对可以正常工作,但对于超过 10 个元素却不能正常工作。我不知道为什么它不起作用,我希望你能帮助我。

谈论问题: 我试图对一个有 10 个元素的浮点数组进行排序。事实上,这不起作用,我试图通过仅使用整数来使其更容易。当我测试它时,我意识到 qsort 通过对数组使用 8 个或更少的元素来工作得很好。当我使用超过 8 个元素时,它根本不起作用。有些元素(总是相同的元素)被排序,而另一些则没有。根本没有正确列出它们。所以我尝试了其他代码来解决问题,但没有一个代码改变了一些东西。

#include <stdio.h>
#include <stdlib.h>

int CompareFloat(const void* pcv1, const void* pcv2);
int CompareIntegers(const void* pcv1, const void* pcv2);

int main()
{
    int aiArr[10] = { 10,9,8,7,5,6,4,2,3,1};
    int aiArr2[8] = { 8,7,6,5,4,2,3,1 };
    float afArr[8] = { 5.0f, 4.611f, 4.61f, 4.1f, 4.0f, 10.0f, 1.9f, 1.8f };
    for (int i = 0; i < 8; i++)
    {
        printf("%f\t", afArr[i]);
    }
    puts("\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%i\t", aiArr[i]);
    }
    puts("\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%i\t", aiArr2[i]);
    }

    qsort(aiArr2, 8, sizeof(int), CompareIntegers);
    qsort(aiArr, 10, sizeof(int), CompareIntegers);
    qsort(afArr, 8, sizeof(float), CompareFloat);
    puts("\n");

    for (int i = 0; i < 8; i++)
    {
        printf("%f\t", afArr[i]);
    }
    puts("\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%i\t", aiArr[i]);
    }
    puts("\n");
    for (int i = 0; i < 8; i++)
    {
        printf("%i\t", aiArr2[i]);
    }

    return 0;
}

int CompareFloat(const void* pcv1, const void* pcv2)
{
    int iRet;

    float* pf1 = (float*)pcv1;
    float* pf2 = (float*)pcv2;

    if (*pf1 < *pf2)
    {
        iRet = -1;
    }
    if (*pf1 > *pf2)
    {
        iRet = 1;
    }
    else
    {
        iRet = 0;
    }

    return iRet;
}
int CompareIntegers(const void* pcv1, const void* pcv2)
{
    int iRet;
    int* pi1 = (int*)pcv1;
    int* pi2 = (int*)pcv2;

    if (*pi1 < *pi2)
    {
        iRet = -1;
    }
    if (*pi1 > *pi2)
    {
        iRet = 1;
    }
    else
    {
        iRet = 0;
    }

    return iRet;

}

输出 (cutt some 0):

1.8000  1.9000  4.0000  4.1000  4.6100  4.6110  5.0000       10.0000

1     3     2     4     5     6     7     8     9       10

1     2     3     4     5     6     7     8

预期产量(削减一些 0):

1.8000  1.9000  4.0000  4.1000  4.6100  4.6110  5.0000  10.0000 

1   2   3   4   5   6   7   8   9   10  

1   2   3   4   5   6   7   8

我正在阅读大量代码和有关 qsort 的更多信息,但它无法正常工作。较大数组的 elemts 没有排序,就像它们应该的那样(我认为是这样)。

C 指针 std quicksort qsort

评论

2赞 Raymond Chen 12/2/2022
在 godbolt 上工作
5赞 Shawn 12/2/2022
比较函数中存在一些逻辑错误。如果第一个参数小于第二个参数,则您的代码实际上说它们是相等的。
1赞 Weather Vane 12/2/2022
因为第二个比较缺乏.else
1赞 Shawn 12/2/2022
@Jabberwocky 第一个是没有意义的;下一个 / 将始终覆盖它设置的值。ififelse
2赞 Jabberwocky 12/2/2022
@Shawn你是对的,但这个问题应该得到一个正确的答案,不应该被关闭。

答:

3赞 Nate Eldredge 12/2/2022 #1

在比较函数中,您在第二个 .elseif

你有:

    if (*pi1 < *pi2)
        iRet = -1;
    if (*pi1 > *pi2)
        iRet = 1;
    else
        iRet = 0;

考虑一下当 .第一个是真的,所以我们设置 .然后我们继续第二个(这是错误)。第二个是假的,所以我们设置 .因此,我们最终返回 0 而不是正确的结果 -1。*pi1 < *pi2ifiRet = -1ififiRet = 0

三向测试应如下所示:

    if (*pi1 < *pi2)
        iRet = -1;
    else if (*pi1 > *pi2) // note else here
        iRet = 1;
    else
        iRet = 0;

因此,只有一个分支执行。

或者,使用“提前退货”:

   if (*p1 < *p2)
      return -1;
   if (*p1 > *p2)
      return 1;
   return 0;

评论

0赞 Jonathan Leffler 12/2/2022
甚至:它有各种有用的更改,但大多比原版短得多。使用也很好。编译器可能优化为仅计算一次,并且每个计算一次。int CompareIntegers(const void *pcv1, const void *pcv2) { int i1 = *(const int *)pcv1; int i2 = *(const int *)pcv2; return (i1 > i2) - (i1 < i2); }if (i1 > i2) return +1; if (i1 < i2) return -1; return 0;*p1*p2
0赞 Nate Eldredge 12/2/2022
@JonathanLeffler:我认为你的优化实际上更糟。任何一个原始版本都编译为一个条件集和一个条件移动。你的编译为两个条件集和一个减法。godbolt.org/z/9qMn53hq3所有这些都优化了 和 的额外负载,这是非常基本的 CSE。你的肯定更短,我认为它是否更具可读性是值得商榷的。*p1*p2
1赞 Nate Eldredge 12/2/2022
为了其他阅读者的利益,我只想对那些在纸面上看起来不错,但可能会溢出并导致未定义行为的看似聪明的人提出通常的警告。return *p1 - *p2;