PHP usort 函数底层排序

xubin · 发表于 2021-12-17 21:24:57

　　最近在一个项目中, 需要对一个数组的顺序进行调整, 允许手动将某一个元素提到数组的开头位置. 在这里, 使用了PHP中的usort函数进行了数组的排序, 代码大致如下:八四论坛https://www.84fzw.net/八四编程论坛关注编程安全和移动安全、程序调试与病毒分析的前沿领域，平台本身资源丰富，作为一个资源平台，为程序员及广大编程爱好者提供了一个氛围良好的交流与合作空间。

　　但是, 今天我大哥突然告诉我, php的usort是不稳定的, 也就是在两个元素相等的情况下, 不能够保证两个元素的位置不变.

　　在我想到的排序算法中:, 其中可以稳定排序的算法有:. 而这几个算法, 时间复杂度较小的是:. 时间复杂度是. 如果要选择一款既能够保证稳定性, 时间复杂度又小的算法, 二者取交集也得选择吧.

　　但是, 毕竟我不是PHP作者, 咱也不知道人家到底用的是什么, 于是乎, 我决定实验一下, 下面这段代码产生了:

　　经过验证, 果然, 我哥诚不欺我. 但是, 我记得我之前也测试过, 数组顺序没有变化啊, 我尝试将数组的长度缩小为4, 突然发现, 是我错了.

　　既然确定了函数是不稳定的排序, 那么他到底是如何进行排序的呢? 我决定尝试着到PHP的源码中挑战一下.

　　到PHP官方将源码下载下来. 解压完了也没太看懂目录结构, 既然知道是c语言写的, 尝试文件夹搜索 array.c , 嗯, 搜到了, 将文件打开. 搜索. 嗯, 有的.

　　再去简单看了一下, 找到真正的排序方法, OK, 再去这个函数里看看. 那么问题来了, 这个函数在哪呢? 找不到? 暴力破解, 简单写了个Python代码, 将所有文件中带有的文件都打印出来:

　　很幸运, 在第一个文件中就找到了.

　　什么? 是个宏? OK, 正好刚写了程序, 我再重新找一下函数在哪里.

　　经过一番苦苦寻找, 终于在「Zend/zend_hash.c」文件下找到了最终的排序算法. 其他的没看懂, 但是, 这里有一句我知道, 是排序的关键:

　　好吧, 又去调函数, 通过查看, 这个sort函数是本函数的第二个参数, 那在返回去看的宏定义, 嗯, 是函数, 成吧, 再去找这个函数. 发现并不在这两个文件下, 再动用我临时写的Python脚本(这都用三次了, 要不我把他好好封装一下). 最终在文件中找到. 到此, 原谅我太菜了, 在自己阅读并进行了大量搜索之后, 还是没太看懂排序的流程.

　　不过, 虽然代码没看懂, 但是, 排序选择的算法我知道了

　　再回想一下, 最开始的问题, 当数组长度小于4的时候, 顺序没有改变, 这个因为使用了稳定的插入排序. 当数组长度100的时候, 使用了不稳定的快速排序.

　　之后使用函数, 就把他当做不稳定的就可以了. 这样基本不会有问题的. 但是, 讲话了, 如果我就是需要一个稳定的排序算法怎么办?

　　来来来, 官方函数推荐给你

　　简单看了一下, 就是一个标准的快排.

　　这次是我的失误, 当初其实想到了排序的稳定性问题, 然后写了个demo验证了一下(就是长度为4的数组), 然后自认为是稳定的, 其实随便到网上搜一下, 都能搜到的问题的. 引以为鉴.

　　最后, 当我google找了一下, 发现第一条搜索就告诉了我, PHP的排序对不同长度分别使用了不同的排序算法. 这就尴尬了. 么事, 虽然最后对算法也没完全看懂, 但乐在其中