C qsort无法正常工作

我不知道我做错了什么,但以下代码没有正确排序数组。

#include  #include  int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } int main() { int x[] = { -919238029, -889150029, -826670576, -579609061, -569653113, -305140505, -216823425, -193439331, -167683147, -49487019, -45223520, 271789961, 275570429, 444855014, 559132135, 612312607, 664554739, 677860351, 1005278191, 1031629361, 1089012280, 1115952521, 1521112993, 1530518916, 1907515865, 1931470931, -1631034645, -1593702794, -1465300620, -1263094822 }; int i; qsort(x, 30, sizeof(int), compare); for(i = 0; i < 30; i ++) printf("%d\n", x[i]); return 0; } 

产生以下输出:

 1521112993 1530518916 1907515865 1931470931 -1631034645 -1593702794 -1465300620 -1263094822 -919238029 -889150029 -826670576 -579609061 -569653113 -305140505 -216823425 -193439331 -167683147 -49487019 -45223520 271789961 275570429 444855014 559132135 612312607 664554739 677860351 1005278191 1031629361 1089012280 1115952521 

我的意思是,问题/必须/在我的比较function。 有人注意到什么奇怪的吗?

是的,你的“比较”溢出了。 🙁

原因:

当您从正数中减去负数时,结果不一定是正数; 如果它不能在数据类型中表示,它将“包围”另一方。

例:

如果你的整数只能保持-8到7(4位),那么当你比较4到-4时会发生什么?
好吧,你得到8,二进制是1000 ,即-8。 所以4小于-4。

道德:

不要做减法而不是比较,即使他们在学校告诉你“看起来有多酷”!

在一般情况下,您不能使用减法来比较整数。 或者,更准确地说,您可以,但仅在您确定减法不会溢出的情况下。 在你的情况下,减法溢出,产生完全没有意义的结果(甚至没有提到当有符号整数减法溢出时,行为是未定义的)。

用于在值ab之间生成三态C型比较的常见习语是(a > b) - (a < b)表达式。 它适用于几乎任何类似类型的数据。 在您的情况下,比较函数可能如下所示

 int compare(const void* a, const void* b) { int va = *(const int*) a; int vb = *(const int*) b; return (va > vb) - (va < vb); } 

我正在使用上面的信息给出一个代码示例。 在我的编译器和系统中,我得到的结果与提出问题的Ram相同。 这表明我的整数类似于Ram的整数。 我沿着Mehrdad建议的行修改了我的代码,使用比较运算符而不是减法运算符。 然后我把数字排序得当。

这是代码:

  #include  #include  int compare(const void* a, const void* b) { int n1 = * (int *) a, n2 = * (int *) b; /* Usine the ternary to express along the lines of if elseif elseif . . . else */ return n1 > n2 // if ? 1 // then : n1 == n2 // else if ? 0 // then : -1 // else ; // end if } int main(int argc, char * argv[]) { int x[] = { -919238029, -889150029, -826670576, -579609061, -569653113, -305140505, -216823425, -193439331, -167683147, -49487019, -45223520, 271789961, 275570429, 444855014, 559132135, 612312607, 664554739, 677860351, 1005278191, 1031629361, 1089012280, 1115952521, 1521112993, 1530518916, 1907515865, 1931470931, -1631034645,-1593702794,-1465300620,-1263094822 }; int i = 0, // index imax = sizeof(x)/sizeof(int); // max value for index FILE * outf = 0; if ( !(outf = fopen("output.txt", "wt")) ) { puts("outf == 0 which is an error trying to open \"output.txt\" for writing.\n"); getch(); return; } qsort(x, imax, sizeof(int), compare); for(i = 0; i < imax; i ++) fprintf(outf, "%d\n", x[i]); fclose(outf); return 0; } 

我得到这个输出:

 -1631034645 -1593702794 -1465300620 -1263094822 -919238029 -889150029 -826670576 -579609061 -569653113 -305140505 -216823425 -193439331 -167683147 -49487019 -45223520 271789961 275570429 444855014 559132135 612312607 664554739 677860351 1005278191 1031629361 1089012280 1115952521 1521112993 1530518916 1907515865 1931470931 

要添加到Mehrad的正确答案,这是一种使用SortChecker在代码中查找错误的自动方法:

 $ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out a.out[38699]: qsort: comparison function is not transitive (comparison function 0x40057d (/home/iuriig/a.out+0x40057d), called from 0x400693 (/home/iuriig/a.out+0x400693), cmdline is "./a.out") -919238029 -889150029 ... 

此警告表示,对于某些输入, compare报告x < y, y < z而不是x < z 。 要进一步调试此问题,请运行

 export SORTCHECK_OPTIONS=raise=1 

并检查生成的codedump。