2

我在 Bentley & McIlroy (1993) 中读到他们建议的快速排序实现在数组变得足够小时时使用插入排序。

我很想知道现代内核是否使用相同的策略。有谁知道Linux内核是否以这种方式从快速排序切换到插入排序？

4

2 回答 2

2

假设您指的是 C 库中的 qsort，这里是qsort()来自最近的 glibc，这是大多数 Linux 系统中使用的：http ://www.cs.umaine.edu/~chaw/200801/capstone/n/qsort .c.html。

它确实切换到小分区的插入。它碰巧使用 4 个元素作为阈值，尽管根据经验选择的数字可能需要更新。

/* Discontinue quicksort algorithm when partition gets below this size.
   This particular magic number was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4
于 2013-10-01T20:31:59.833 回答
2

如果您指的是 Linux 标准 C 库 (GLIBC) 中的 qsort，它实际上是作为合并排序实现的，而不是快速排序。如果它无法为合并排序分配足够的内存，它只会退回到就地快速排序。

不相信我？qsort()在此处查看 GLIBC的源代码：http: //sourceware.org/git/ ?p=glibc.git;a=blob;f=stdlib/msort.c;hb=HEAD#l306

qsort()Mats Linander 有一篇很棒的文章在这里总结了不同标准 C 库中的各种实现：http: //calmerthanyouare.org/2013/05/31/qsort-shootout.html（提示：大多数实际上并不使用快速排序！）

于 2015-11-01T19:05:14.100 回答