php排序稳定性问题
最近在工作中碰到一个挺有意思的问题，线上输入是一串排好序的关联数组，经过一系列处理后输出的数组却是乱序，且本地运行无法复现。查看相关代码后，最让人在意的是这一段:
$categories = Arr::sort($categories, function ($node) {
return $node['default'];
}, true);作用是按default优先级将元素提到前面，首先确认了下线上的illuminate/support版本和本地一致，查看Arr::sort()源码:
...
$descending ? arsort($results, $options)
: asort($results, $options);最终还是调用 php 的asort，线上是 php5 而本地和测试因为最近考虑升级都换成了 php7，最后在 php5 环境下成功复现，确定出是sort问题。
在排序前后相等的元素相对位置不变即说这个算法是稳定的。
对快速排序有一定了解的话可以知道，快速排序是不稳定的所以这段代码在元素default优先级都相同的情况下输出将不会是之前的顺序，但在 php7 环境下测试结果为什么会保留原来的顺序呢。难道关于我之前理解的天底下所有默认排序都是快速排序这一点是错的吗?
立即学习“PHP免费学习笔记（深入）”；
好吧，让我们来快速看看 php 源码是如何解决这个问题的。到 github 官方的 php-src 直接搜索asort in this repository，找c文件，找到这个函数定义在 arr.c:814
PHP_FUNCTION(asort)
{
zval *array;
zend_long sort_type = PHP_SORT_REGULAR;
bucket_compare_func_t cmp;
ZEND_PARSE_PARAMETERS_START(1, 2)
Z_PARAM_ARRAY_EX(array, 0, 1)
Z_PARAM_OPTIONAL
Z_PARAM_LONG(sort_type)
ZEND_PARSE_PARAMETERS_END();
// 设置比较函数
cmp = php_get_data_compare_func(sort_type, 0);
zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);
RETURN_TRUE;
}可以看到最终调用的是zend_hash_sort()，我们继续搜索:
发现这个函数是zend_hash_sort_ex()的套娃，最后找到zend_hash.c:2497
一、源码特点企业费用管理系统，有权限分配，登陆验证，新增角色，发布公告等二、功能介绍1、js的兼容性有个地方不行（比如模块排序，那个时候也是雏鸟一只，写了一小撮，现在用jq应该好处理的吧，ie里面没问题，大家发挥吧）2、里面的菜单和对应菜单下面的目录项可以根据需求自己添加的，有对应模块3、可以根据自己设定的角色添加对应的访问页面4、有些操作涉及到按钮权限，对于这种思路，我粗粗的写了2个自定义控件，
ZEND_API void ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, zend_bool renumber)
{
Bucket *p;
uint32_t i, j;
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) {
/* Doesn't require sorting */
return;
}
// 这里的hole指数组元素被unset掉产生的洞
if (HT_IS_WITHOUT_HOLES(ht)) {
/* Store original order of elements in extra space to allow stable sorting. */
for (i = 0; i < ht->nNumUsed; i++) {
Z_EXTRA(ht->arData[i].val) = i;
}
} else {
/* Remove holes and store original order. */
for (j = 0, i = 0; j < ht->nNumUsed; j++) {
p = ht->arData + j;
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue;
if (i != j) {
ht->arData[i] = *p;
}
Z_EXTRA(ht->arData[i].val) = i;
i++;
}
ht->nNumUsed = i;
}
sort((void *)ht->arData, ht->nNumUsed, sizeof(Bucket), (compare_func_t) compar,
(swap_func_t)(renumber? zend_hash_bucket_renum_swap :
((HT_FLAGS(ht) & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));
...好耶！，官方注释里就有说明是怎么实现排序的稳定性，在排序之前用这个Z_EXTRA保留了原数组元素到下标的映射。
但当我搜索这块代码提交信息时发现了一个问题：稳定排序相关的 rfc 在https://wiki.php.net/rfc/stable_sorting，可以看到是发生在今年五月份且针对 php8.0 的。
?? 那之前的 php7 排序稳定是怎么回事。
马上构造个例子：
$count = 10;
$cc = [];
for ($i=0; $i<$count; $i++) {
$cc[] = [
'id' => $i,
'default' => rand(0, 10),
];
}
$cc = Arr::sort($cc, function ($i) {
return $i['default'];
});
dd($cc);经过多次在 php7 下的测试发现：当$count比较小的时候，排序才是稳定的，但$count较大情况下的排序又变成不稳定。也就是线上排序不稳定而本地无法复现其实是用例的数组长度太短所致。
看到这里可以确定是快速排序长度阈值优化的问题，最后查了下相关资料。php7 中的sort是基于LLVM中libc++的std::sort实现。当元素数量小于等于16时候有特殊优化，大于16才走快速排序，而 php5 是直接就走快速排序的。
$i,
'default' => rand(0, 10),
];
}
usort($cc, function($a, $b){
if ($a['default'] == $b['default']) return 0;
return ($a['default'] < $b['default']) ? 1 : -1;
});
print_r($cc);最后在 php8 环境下试了试，排序绝对稳定
