PHP usort 函数底层排序 _PHP

引出最近在一个项目中, 需要对一个数组的顺序进行调整, 允许手动将某一个元素提到数组的开头位置. 在这里, 使用了php中的usort函数进行了数组的排序, 代码大致如下:
usort($arr, function ($a, $b){// 这里添加了 order 字段, 默认为0, 将order大的提到前边return $b['order'] - $a['order'];});但是, 今天我大哥突然告诉我, php的usort是不稳定的, 也就是在两个元素相等的情况下, 不能够保证两个元素的位置不变.
在我想到的排序算法中: 选择, 冒泡, 插入, 快排, 希尔, 堆排, 计数, 归并, 其中可以稳定排序的算法有: 冒泡, 插入, 归并. 而这几个算法, 时间复杂度较小的是: 快排, 归并, 堆排. 时间复杂度是O(log n). 如果要选择一款既能够保证稳定性, 时间复杂度又小的算法, 二者取交集也得选择归并吧.
但是, 毕竟我不是PHP作者, 咱也不知道人家到底用的是什么, 于是乎, 我决定实验一下, 下面这段代码产生了:
// 生成一个随机数组$arr = [];for ($j = 0; $j < 100; $j++){$arr[] = ['id' => $j,'order' => random_int(0, 3),];}// 按照order进行排序usort($arr, function ($a, $b){return $b['order'] - $a['order'];});// 验证是否稳定$lastValue = https://www.isolves.com/it/cxkf/yy/php/2020-05-03/null;foreach ($arr as $value){if(empty($lastValue)){$lastValue = $value;continue;}// 若当前元素与上一个元素order相同, 判断if($value['order'] == $lastValue['order']){// 当前不稳定了, 把数组打印出来if($value['id'] < $lastValue['id']){echo '不稳定', PHP_EOL;exit;}}$lastValue = $value;}经过验证, 果然, 我哥诚不欺我. 但是, 我记得我之前也测试过, 数组顺序没有变化啊, 我尝试将数组的长度缩小为4, 突然发现, 是我错了.
分析既然确定了usort函数是不稳定的排序, 那么他到底是如何进行排序的呢? 我决定尝试着到PHP的源码中挑战一下.
到PHP官方 https://www.php.net/downloads 将源码下载下来. 解压完了也没太看懂目录结构, 既然知道是C语言写的, 尝试文件夹搜索 array.c , 嗯, 搜到了, 将文件打开. 搜索 usort. 嗯, 有的.

文章插图
【PHP usort 函数底层排序】
再去 php_usort 函数看看:

static void php_usort(INTERNAL_FUNCTION_PARAMETERS, compare_func_t compare_func, zend_bool renumber) /* {{{ */{	zval *array;	zend_array *arr;	zend_bool retval;	PHP_ARRAY_CMP_FUNC_VARS;	PHP_ARRAY_CMP_FUNC_BACKUP();	// 这个 zend 打头的函数一看就是虚拟机相关的, 不管了	ZEND_PARSE_PARAMETERS_START(2, 2)Z_PARAM_ARRAY_EX2(array, 0, 1, 0)Z_PARAM_FUNC(BG(user_compare_fci), BG(user_compare_fci_cache))	ZEND_PARSE_PARAMETERS_END_EX( PHP_ARRAY_CMP_FUNC_RESTORE(); return );	arr = Z_ARR_P(array);	// 一看就是对数组进行判空, 跳过	if (zend_hash_num_elements(arr) == 0){PHP_ARRAY_CMP_FUNC_RESTORE();RETURN_TRUE;	}	/* Copy array, so the in-place modifications will not be visible to the callback 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 文件中找到. 到此, 原谅我太菜了, 在自己阅读并进行了大量搜索之后, 还是没太看懂排序的流程.
不过, 虽然代码没看懂, 但是, 排序选择的算法我知道了