为什么qsort()没有返回值？

Question

我大部分时间都是C++程序员，但为了好玩，我尝试在C语言中进行一些通用编程。特别是，我实现了一个通用排序算法。我的函数签名是：

int sort(void   *data,
         size_t num_elems,
         size_t elem_size,
         int    (*cmp)(const void*, const void*))

与标准库中的 qsort() 相比，我注意到我的函数与其不同，qsort() 没有返回值。由于对数组进行排序总是需要交换元素，因此实现需要一个大小为 elem_size 的临时存储器。由于 C 语言没有模板，所以在编译时不知道 elem_size 的大小，因此必须动态分配临时存储器，这可能失败。在这种情况下，qsort() 不能对数组进行排序，并且也无法报告错误，因此无法确定在返回后数组是否已排序。

我有遗漏什么吗？

- cthl

---

请您能详细说明一下吗？如何在不使用额外存储空间的情况下改变元素的顺序，至少需要改变一个元素的位置？ - cthl

不要理会那句话，我很蠢，误以为你写的是“num_elems”而不是“elem_size”。然而，即使没有可变量大小的临时存储，仍然可以交换任意数量的内存，只需按固定大小单位进行交换（例如一次一个字节）。 - Ry-

Answer 1

任何分区算法都需要能够交换两个元素，而 qsort API 意味着代码在编译时不知道它们的大小。但它们不必全部交换; 它们可以逐字节交换。(这实际上是 memcpy 的做法。)

下面的注释和宏定义在 GNU libc 实现的 qsort.c 开始处就存在。(注意，该代码受 LGPL 保护)

/* Byte-wise swap two items of size SIZE. */
#define SWAP(a, b, size)                                                      \
  do                                                                          \
    {                                                                         \
      size_t __size = (size);                                                 \
      char *__a = (a), *__b = (b);                                            \
      do                                                                      \
        {                                                                     \
          char __tmp = *__a;                                                  \
          *__a++ = *__b;                                                      \
          *__b++ = __tmp;                                                     \
        } while (--__size > 0);                                               \
    } while (0)

- rici

---

谢谢，那确实解决了问题。我想知道为什么我自己没有想到。 - cthl

@cthl：一旦你看到了，一切都显而易见。我们中的每个人都曾因没有第一个看到它而自责无数次。 - rici

Answer 2

这个函数不会失败 -- 除非参数无效，否则它的行为是未定义的，而且该函数也无法可靠地检测到。

qsort本身不分配任何内存。(当然，它可以做任何事情，但它不允许因为内存分配失败而失败，所以实现者必须考虑到这一点)。

- M.M

---

但是，如何在没有内存分配的情况下实现排序算法呢？任何实现都需要改变元素的顺序，因此需要一个地方暂时存储至少一个元素。 - cthl

它可以逐个字节地进行交换。 - rici

它可以使用CPU寄存器，例如。或者它可以执行XOR技巧。 - M.M

@cthl 我期望 qsort() 使用一个小的固定大小缓冲区，比如16，并通过该缓冲区进行交换，而不是每次使用1个字节 - 如有需要，在循环中使用该缓冲区。 - chux - Reinstate Monica

@chux：Gnu实现使用宏引用我的答案，因此确实是一次一个字节。FreeBSD版本使用long或int，如果向量的大小和地址是其各自类型大小的倍数。在具有整数类型陷阱表示的系统上，这将是UB；如果您想避免UB，则必须使用memcpy，此时您可能会使用一次一个字节的版本。 - rici

请注意，您甚至可以使用此方法进行循环，而不仅仅是交换。https://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c - R.. GitHub STOP HELPING ICE