PHP的usort应用哪些排序算法？

Question

我希望按照修改时间升序和降序对文件进行排序。

根据这个答案，最好定义一个排序回调函数并使用usort/uasort来实现。

然而，由于我的应用程序的性质，我可能会遇到某些最坏情况的排序算法（例如几乎相反顺序的输入序列）。

因为每次比较都使用两个部分在网络驱动器上的文件系统访问，所以比较次数至关重要，必须最小化。其他类型的迭代可能更多。

那么PHP的数组排序函数使用了哪些排序算法呢？快速排序？多路排序？有没有办法可以配置它？

在排序之前，我应该将数组洗牌吗？

还是我需要编写自己的实现？

您知道一些提供可配置算法的排序功能的好库吗？

您推荐哪种算法或解决此问题的方法来最小化比较？

- The Surrican

---

我在我的博客中写了关于它的内容：http://murilo.wordpress.com/2011/02/05/phps-sort-functions-are-bad-designed/ 请看一下。 - Murilo Vasconcelos

Answer 1

我在 php.net/sort 上找到了以下内容：

注意：和大多数 PHP 排序函数一样，sort() 使用的是 » 快速排序算法的实现。

我认为它使用的是 随机快速排序，因此不需要对数组进行洗牌。

我进行了 一些测试 发现 PHP 的快速排序算法并非随机的，因此请先将输入数组洗牌！！

- Murilo Vasconcelos

Answer 2

我使用PHP OpenGrok进行了几次搜索，基于一些函数名称的瞥见和代码的浏览，看起来usort是用快速排序实现的。

为了最小化文件系统调用，在数组的每个项目中只进行一次调用，并将结果存储在另一个数组中。在比较器函数中使用第二个数组，而不是再次进行调用。

- Dan Grossman

---

谢谢。缓存确实是个好主意 :D 我太蠢了，竟然没想到，这么明显的事情。 - The Surrican

那么为什么你会接受另一个回答呢？它是在我的回答之后写的，而且说的也是同样的意思。 - Dan Grossman

Answer 3

所以我认为通过检查PHP代码的内部工作方式，我得到了答案。

当你调用uasort时，以下是发生的事情：

uasort > php_usort > zend_hash_sort > zend_hash_sort_ex > sort > auxsort

然后，你需要打开https://github.com/lua/lua存储库来弄清楚auxsort是一个简单的快速排序算法（递归函数）。

此外，有趣的是要知道'pivot'已经通过choosePivot函数进行了随机化，所以当给定数组已经排序时，你不会遇到O(n^2)复杂度的最坏情况。

- vincent PHILIPPE