对混洗数组进行排序所需的比较次数：qsort 与 std::sort

给定一个包含N个double类型的数组，在 C 中对其进行排序的标准方法是调用qsort函数

qsort （数组， N ， sizeof （双） ，比较） ；   

其中compare是一个函数，如果第一个参数小于、等于或大于第二个参数，则返回一个小于、等于或大于零的整数。因为它是一个 C 函数，所以它接受 void 指针，我们必须将其转换回实际值。实现这种转换的一种安全方法是通过memcpy函数。下面是一个比较函数的合理实现：

 int比较( const void * a , const void * b ) {     双x , y ;     memcpy ( & x , a , sizeof ( x ) ) ;     memcpy ( & y , b , sizeof ( y ) ) ;     计数器+ + ;     如果( x < y ) {返回- 1 ; }     如果( x = = y ) {返回0 ; }     返回1 ;   }   

尽管该函数似乎有分支，但在这种情况下优化编译器可以生成二进制代码而无需任何跳转。

虽然名称暗示qsort可能使用教科书算法Quicksort来实现，但实际实现取决于标准库。

C++ 中的标准方法是类似的。代码可能如下所示：

标准：：排序（数组，数组+ N ，比较） ；   

同样，我们有一个比较功能。在 C++ 中，比较函数可以直接引用类型，因为std::sort实际上是一个模板函数，而不仅仅是一个函数。它使 C++ 编译器有效地为您提供的每个比较函数生成一个函数。它以增加二进制大小换取潜在的性能提升。比较函数的合理实现如下：

布尔比较（常量双x ，常量双y ） {     返回x < y ;   }   

C++ 比较函数的签名不同：我们返回一个布尔值，而不是一个三类整数值。

一个有趣的问题是每个函数进行多少次比较。通常，比较价格不高，并且是性能的不良预测指标，但您可以想象比较您的值可能很昂贵的情况。

比较的确切数量取决于您的系统提供的底层实现。作为输入，我使用随机数组。

我选择计算调用比较函数的平均次数。通过实验，我发现 C++ 函数对比较函数的调用比 C 函数 ( qsort ) 的调用次数多得多。 GCC (glibc) 附带的 C 库平均每个元素使用k – 1.2645 次比较来对大小为 2 ^k的数组进行排序，与合并排序的理论平均案例性能相匹配。

LLVM 13（苹果）：

海湾合作委员会 9：

我的代码可用。

进一步阅读。

• Travis Downs击败 Qsort
• Mats Linander的 libc qsort() 枪战

原文： https://lemire.me/blog/2022/10/11/the-number-of-comparisons-needed-to-sort-a-shuffled-array-qsort-versus-stdsort/