PHP usort() 相等情况下的顺序

Question

在 PHP 中 manual for usort() ，它指出:

If two members compare as equal, their relative order in the sorted array is undefined.

此外，

A new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal.

那么我的问题是:如果两个元素相等(例如，用户定义的函数返回 0)会怎样？我正在使用此函数，显然相等的项目随机排列在已排序的数组中。

Answer 1

注意不要混淆“未定义”和“随机”。

一个随机的实现确实应该每次都给出不同的顺序。这意味着当发现它们相等时，有特定的代码来洗牌结果。这会使算法更复杂、更慢，而且很少会是理想的结果。

undefined 的意思恰恰相反:在设计具有可预测或稳定顺序的算法时完全没有注意。这意味着每次运行结果可能都不同，如果这恰好是算法对该数据的副作用。

可以看到the core sort implementation in the PHP source code .它混合了“快速排序”(分而治之)和插入排序(一种对短列表有效的更简单的算法)以及针对 2、3、4 和 5 个元素列表的手动优化例程。

因此，相等成员的确切行为将取决于列表的大小、这些相等成员在列表中的位置、一批中有多少相等成员等因素。在某些情况下，算法会看到它们是相同的，而不是交换它们(理想情况下，因为交换需要时间)；在其他情况下，它不会直接比较它们，直到它们已经相对于其他事物移动，所以它们最终会以不同的顺序结束。