00-1010最近，在一个项目中，有必要调整数组的顺序，允许将一个元素手动提升到数组的开头。这里用PHP中的usort函数对数组进行排序，代码大致如下：
usort ($ arr ), function ($ a ,$ b)
//这里增加了订单字段，默认值为0，指的是傲慢的冰棍的大订单。
返回$ b[' order ']-$ a[' order ']；
});
但是今天我大哥突然跟我说php的usort不稳定，就是两个元素相等的时候，不能保证两个元素的位置不变。
我想到的排序算法中，是选择、冒泡、插入、快速排序、希尔、堆叠、计数、合并，其中：是可以稳定排序的算法。然而，在这些算法中，是快速排序、合并和堆叠，时间复杂度更低。时间复杂度为0(对数n)。如果要选一个，可以保证。
但是毕竟我不是PHP作者，也不知道别人在用什么，所以决定实验一下，下面的代码就产生了：
//生成随机数组
$ arr=[]；
for($ j=0；100牙买加元；$ j){ 0
$arr[]=[
id'=$j，
order'=random_int(0，3)，
];
}
//按顺序排序
usort ($ arr ), function ($ a ,$ b)
返回$ b[' order ']-$ a[' order ']；
});
//验证是否稳定
$ lastValue=null
foreach ($arr为$ value){ 0
if(空($ LastVaLue)){ 0
$ lastValue=$ value
继续；
}
//如果当前元素与前一个元素顺序相同，则判断
if($ value[' order ']=$ last value[' order ']){ 0
//当前不稳定，打印出数组。
if($ value[' id ']$ LastValue[' id ']){ 0
Echo '不稳定'，PHP _ EOL
退出；
}
}
$ lastValue=$ value
}
经过验证，果然，甜蛋挞不骗我。不过我记得我之前测试过，数组顺序没变。我试图把数组的长度减少到4，突然发现我错了。
引出
既然确定了usort函数是一个不稳定的排序，那么它是如何排序的呢？我决定尝试挑战PHP源代码。从PHP官方https://www.php.net/downloads.下载源代码解压后我不太明白目录结构。现在知道是用C语言写的，我试着在文件夹里搜索array.c。好吧，如果我找到了，打开文件。搜索我们的网站。嗯，有。
转到php_usort函数查看：
static void PHP _ usort(INTERNAL _ FUNCTION _ PARAMETERS，compare_func_t compare_func，zend_bool重新编号)/* {{{ */
{
zval *数组；
zend _ array *
zend _ bool retval
VARS FUNC；
PHP _ ARRAY _ CMP _ FUNC _ BACKUP()；
//这个zend函数乍一看和虚拟机有关，不管不顾。
ZEND_PARSE_PARAMETERS_START(2，2)
Z_PARAM_ARRAY_EX2(数组，0，1，0)
Z_PARAM_FUNC(BG(用户_比较_fci)，BG(用户_比较_ fci _缓存))
ZEND _ PARSE _ PARAMETERS _ END _ EX(PHP _ ARRAY _ CMP _ FUNC _ RESTORE()；返回)；
arr=Z_ARR_P(数组)；
//乍一看，是清空数组，跳过它。
if(Zend _ hash _ num _ elements(arr)=0){ 0
PHP _ ARRAY _ CMP _ FUNC _ RESTORE()；
返回_真；
}
/*复制数组，因此回调看不到就地修改
function */ arr = zend_array_dup(arr); // 真正进行排序的方法 retval = zend_hash_sort(arr, compare_func, renumber) != FAILURE; // 一些善后操作 zval_ptr_dtor(array); ZVAL_ARR(array, arr); PHP_ARRAY_CMP_FUNC_RESTORE(); RETURN_BOOL(retval); }简单看了一下, 找到真正的排序方法zend_hash_sort, OK, 再去这个函数里看看. 那么问题来了, 这个函数在哪呢? 找不到? 暴力破解, 简单写了个Python代码, 将所有文件中带有 zend_hash_sort 的文件都打印出来:
很幸运, 在第一个文件中就找到了.
什么? 是个宏? OK, 正好刚写了程序, 我再重新找一下 zend_hash_sort_ex 函数在哪里.
经过一番苦苦寻找, 终于在 Zend/zend_hash.c 文件下找到了最终的排序算法. 其他的没看懂, 但是, 这里有一句我知道, 是排序的关键:
好吧, 又去调 sort函数, 通过查看, 这个sort函数是本函数的第二个参数, 那在返回去看zend_hash_sort的宏定义, 嗯, 是 zend_sort 函数, 成吧, 再去找这个函数. 发现并不在这两个文件下, 再动用我临时写的Python脚本(这都用三次了, 要不我把他好好封装一下??). 最终在Zend/zend_sort.c 文件中找到. 到此, 原谅我太菜了, 在自己阅读并进行了大量搜索之后, 还是没太看懂排序的流程.
不过, 虽然代码没看懂, 但是, 排序选择的算法我知道了
若数组长度小于等于16, 使用 插入排序若数据长度大于16, 使用 快速排序 (快速排序对元素个数1024前后做了不同的处理, 应该是优化)总结
再回想一下, 最开始的问题, 当数组长度小于4的时候, 顺序没有改变, 这个因为使用了稳定的插入排序. 当数组长度100的时候, 使用了不稳定的快速排序.
之后使用usort函数, 就把他当做不稳定的就可以了. 这样基本不会有问题的. 但是, 讲话了, 如果我就是需要一个稳定的排序算法怎么办?
来来来, 官方函数推荐给你https://www.php.net/manual/zh/function.uasort.php
If you want to keep the order when two members compare as equal, use this. <?php function stable_uasort(&$array, $cmp_function) { if(count($array) < 2) { return; } $halfway = count($array) / 2; $array1 = array_slice($array, 0, $halfway, TRUE); $array2 = array_slice($array, $halfway, NULL, TRUE); stable_uasort($array1, $cmp_function); stable_uasort($array2, $cmp_function); if(call_user_func($cmp_function, end($array1), reset($array2)) < 1) { $array = $array1 + $array2; return; } $array = array(); reset($array1); reset($array2); while(current($array1) && current($array2)) { if(call_user_func($cmp_function, current($array1), current($array2)) < 1) { $array[key($array1)] = current($array1); next($array1); } else { $array[key($array2)] = current($array2); next($array2); } } while(current($array1)) { $array[key($array1)] = current($array1); next($array1); } while(current($array2)) { $array[key($array2)] = current($array2); next($array2); } return; }简单看了一下, 就是一个标准的归并排序.
这次是我的失误, 当初其实想到了排序的稳定性问题, 然后写了个demo验证了一下(就是长度为4的数组), 然后自认为是稳定的, 其实随便到网上搜一下, 都能搜到的问题的. 引以为鉴.
最后, 当我google找了一下, 发现第一条搜索就告诉了我, PHP的排序对不同长度分别使用了不同的排序算法. 这就尴尬了. 么事, 虽然最后对算法也没完全看懂, 但乐在其中