C 中的 qsort 使用两倍的内存量

Question

我有一个程序，我需要在 RAM 中读取数据字节，使用 qsort 对数据进行排序，然后将数据写回文件，问题是我只允许使用一定数量的记忆这样做。这是我所做的一些事情：

FILE *fp;
/* open file for reading up here , blah blah blah*/
...

int mb = 1024*1024;
int mem_size = 20*mb;
int total_cookies = mem_size/sizeof(Cookie);
Cookie *buffer = (Cookie *) calloc(total_cookies, sizeof(Cookie));

/* read bytes into buffer*/
 while ((result = fread(buffer, total_cookies , sizeof(Cookie), fp)) > 0) {
      qsort(buffer, total_cookies, sizeof(Cookie), compare);
      fwrite(....)
 }
 free(buffer);

我的问题是，当我运行我的程序针对 /usr/bin/time -v 并检查最大驻留集大小时，我使用了两倍于我预期的内存量，问题点回到 qsort 函数。

如何让 qsort 就地排序，而不使用额外的内存？

Answer 1

由于规范中没有关于内存消耗或时间复杂度的要求，如果您对内存消耗有限制（至少如果您想要可移植性），您将需要使用另一个函数（可能是自行实现的）。

确实存在具有 O(n log n) 复杂性和 O(n log n) 内存消耗的算法（fx 快速排序）。可能有实际使用这种算法来实现 qsort 的实现，但您的实现可能是其中的 none。

还有其他需要更多内存的体面算法。例如，合并排序需要为最后一个合并步骤制作数据副本（这与您的观察结果一致）。归并排序有它的优势（例如，最坏情况时间复杂度更好），这可能是实现选择该算法的原因。

实际上，qsort 的实施在时间和记忆方面都可能比它差很多。 qsort 就地排序的说法仅在结果最终与输入位于同一数组中的情况下才是正确的，但在此之前它可能会将数据分散到各处。

C 中的 qsort 使用两倍的内存量

qsort in C uses twice the amount of memory

c

memory

memory-management

quicksort

qsort