0

从这个链接

因为这个函数可能被优化为使用非线性搜索算法（可能是二分搜索），所以使用比较小于键的元素应该在比较相等的元素之前，而这些应该在比较大的元素之前。使用与比较使用的相同标准排序的任何数组都满足此要求（就像使用 qsort 排序一样）。

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

3 回答 3

1

在引用的文本中，斜体部分是什么意思？

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

（请注意，这些词只告诉您compar报告小于或大于的元素的排序。它不会对compar报告为相等的元素的排序施加任何限制。）

另外，我可以订购数组后代吗？还是只有上升？

该compar函数定义了排序是什么。您可能会认为 3 < 4 或“apple”在“banana”之前，但compar可以是任何顺序。为此，“上升”是指按定义的顺序进展；它并不一定意味着 3 在 4 之前或“apple” 在“banana”之前。例如，您可以先根据整数的低位，然后是第二低位，然后是第三低位，依此类推，而不是按照通常的值对整数进行排序。

被排序的数组中的元素还能是什么顺序呢？

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

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

于 2020-12-31T14:19:36.753 回答
1

这部分报价

使用比较小于键的元素应该在那些比较相等的元素之前，这些应该在那些比较大的元素之前。

qsort表示数组的排序方式应使得根据所使用的比较函数（指定为标准函数和调用的参数的函数）“小于”键的所有元素bsearch必须位于“根据相同的比较函数，equal" 到 key 并且根据比较函数，最后一个依次必须位于大于 key 的元素之前。

当我们谈论数组元素的升序或降序时，我们的意思是为数组元素定义了运算符<（不需要内置运算符<，而是一些用户定义的函数），这样对于升序，这种关系!( 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进行二分搜索，那么您应该提供数组的顺序，指定适当的比较函数，这样

使用比较小于键的元素应该在那些比较相等的元素之前，这些应该在那些比较大的元素之前。

也就是说，在使用函数时，总是假设bsearch数组根据比较函数按升序排序。

于 2020-12-31T14:34:46.897 回答
0

在引用的文本中，斜体部分是什么意思？

数组的排序必须与qsort使用相同的compar函数一样。注意：所有可能的qsort结果都是好的，不管原始数组顺序（可能给出不同的结果，但仍然是好的顺序bsearch）。

另外，我可以订购数组后代吗？还是只有上升？

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

被排序的数组中的元素还能是什么顺序呢？

没有，但请注意qsort，相同元素的多个初始顺序可能会产生多个结果。

于 2020-12-31T13:43:33.320 回答