是否可以同时对数组进行排序以使 bsearch 起作用？

Question

Because this function may be optimized to use a non-linear search algorithm (presumably a binary search), the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater. This requirement is fulfilled by any array ordered with the same criteria used by compar (as if sorted with qsort).

在引用的文字中，斜体部分是什么意思？
另外，我可以订购数组后代吗？还是上升？
被排序的数组里面的元素还能是什么顺序？

Answer 1

In the quoted text, what does it mean the italic part?

必须使用与 qsort 相同的 compar 函数对数组进行排序。 注意： 所有可能的 qsort 结果都适用于此，无论原始数组顺序如何（这可能会给出不同的结果，但对于 bsearch 仍然是好的顺序）。

Also, can I order the array descendant? or only ascendant?

仅与 qsort 使用相同的比较函数（又名：它必须是升序）。

What else kind of order can the elements inside the array being sorted can it be?

None，但请注意，多个 qsort 结果可能与相同元素的多个初始顺序有关。

Answer 2

In the quoted text, what does it mean the italic part?

文本“使用 compar 比较小于键的元素应该在比较相等的元素之前，并且这些应该在比较更大的元素之前”意味着如果你有两个元素的数组，说 a[i] 和 a[j]，并且 compar 报告 a[i] 是“小于” a[j]，那么 i 应该小于j（按其整数值），并且，如果 compar 报告 a[i]“大于”a[j]，则 i 应大于 j.换句话说，数组中元素位置之间的关系与 compar.

报告的它们的值之间的关系相匹配

（请注意，这些词仅告诉您有关 compar 报告为小于或大于的元素的排序。它不会对 compar 报告为的元素的排序施加任何约束等于。）

Also, can I order the array descendant? or only ascendant?

compar函数定义排序是什么。你可能在脑海中有一些想法，即 3 < 4 或“苹果”在“香蕉”之前，但 compar 可以是任何顺序。为此，“升序”表示按定义的顺序进行；它并不一定意味着 3 在 4 之前或“苹果”在“香蕉”之前。例如，您可以先根据低位对整数进行排序，然后是第二低位，然后是第三低位，依此类推，而不是按照通常的值排序。

What else kind of order can the elements inside the array being sorted can it be?

可以使用任何总排序。总排序给出了任意两个元素（<、= 或>）之间的一种关系，并且不包含任何“矛盾”以将元素排序。形式上，对于任何 x、y 和 z，全序满足：x ≤ y 和 y ≤ x 意味着 x = y，x ≤ y 和 y ≤ z 意味着 x ≤ z，并且 x ≤ y 或 y ≤ x。

可以使用满足这些要求的任何关系。

Answer 3

这部分引用

the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater.

意味着数组应该按照使用的比较函数（指定为标准函数调用的参数的函数 qsort 和 bsearch) 必须先于根据相同比较函数“等于”键的元素，而最后一个元素必须先于根据比较函数“大于”键的元素。

当我们谈论数组元素的升序或降序时，我们的意思是为数组元素定义了运算符 <（不需要内置运算符 <，而是一些用户定义的函数），这样对于升序，此关系为 !( a[j] < a[i] )，其中 i < j 为数组的所有元素保留，而对于降序，关系为 !( a[i] < a[j] )

对于标准函数qsort和bsearch，设置顺序的比较函数声明和定义如下

int cmp(const void *, const void *)

如果第一个指向的元素（或 bsearcj 的键）被认为分别小于、匹配，或者大于第二个指向的数组元素。

例如，您可以使用函数 qsort 根据某些标准对数组进行分区。

这是一个演示程序，它首先根据每个具有奇数值的元素“小于”每个具有偶数值的元素的标准对数组进行排序，然后反之亦然。

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

int cmp1( const void *left, const void *right )
{
    int a = *( const int * )left;
    int b = *( const int * )right;
    
    return b % 2 - a % 2;
}

int cmp2( const void *left, const void *right )
{
    return -cmp1( left, right );
}

int main(void) 
{
    enum { N = 10 };
    int a[N];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % N;
    }
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    qsort( a, N, sizeof( int ), cmp1 );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    qsort( a, N, sizeof( int ), cmp2 );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    return 0;
}

程序输出可能看起来像

4 8 8 9 5 2 9 0 1 2 
9 5 9 1 4 8 8 2 0 2 
4 8 8 2 0 2 9 5 9 1

您可以使用函数bsearch和相应的比较函数来查找具有指定键的元素。

在这个例子中这个数组

9 5 9 1 4 8 8 2 0 2

根据函数cmp1和这个数组

升序排列

4 8 8 2 0 2 9 5 9 1

根据函数cmo2.

升序排列

另一方面，您可以考虑第一个数组相对于第二个数组按升序排序，而第二个数组根据比较函数cmp1按降序排序。反之亦然，如果考虑根据比较函数 cmp2.

对数组进行排序

但是，如果您使用函数 bsearch 进行二分查找，那么您应该提供数组的顺序，指定适当的比较函数，这样

the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater.

也就是当你使用函数bsearch时总是假定数组是根据比较函数升序排列的

是否可以同时对数组进行排序以使 bsearch 起作用？

Can an array be ordered both ascendant and descendant for bsearch to work?

c

bsearch