排序算法 - PHP 数组排序函数 sort 底层实现分析

数据结构与算法系列（十三）

前面我们已经介绍了线性表（即线性数据结构，如数组和链表）的常规排序算法，包括冒泡、插入、选择、归并和快排，其中综合性能最好的就是快排（快速排序），所以快排在工程实践中也有大量的应用，比如很多编程语言都提供了排序函数，而这些排序函数基本都是基于快速排序实现的，比如 PHP 的数组排序函数 sort 就是如此，今天我们将以此函数的底层实现为例，为大家展示如何基于快速排序来实现 PHP 的 sort 函数（准确的说，是综合运用了插入排序和快速排序）。

首先我们来给大家介绍下 sort 函数，该函数的函数签名是这样的：

bool sort ( array &$array [, int $sort_flags = SORT_REGULAR ] )

我们在调用该函数时，需要传递一个数组作为第一个参数，并且该参数是一个引用参数，不需要设置返回值，排序结果直接作用在数组本身上。该函数默认对数组内数据进行升序排序，支持对数字和字符串进行排序，更多细节可以参考官方文档：PHP: sort - Manual

平时，我们想要对数据进行排序的时候可能就直接拿来用了，很少有人会去关注该函数的底层是如何实现的，就着我们刚学习完的排序算法，正好趁热打铁，研究下它的底层实现。

由于 sort 函数的实现隐藏在 PHP 底层核心代码中，所以首先我们要把 PHP 源码下载到本地，PHP 底层源码已经公布到 GitHub 上：GitHub - php/php-src: The PHP Interpreter，你可以自行将其下载到本地以方便查看，PHP 源码基于 C 语言编写，所以你需要一个支持 C/C++ 语言解析的编辑器来查看 PHP 源码，比如 Visual Studio Code、Visual C++、CLion 等。

PHP 源码中 sort 函数定义位于头文件 ext/standard/php_array.h 中（其实数组相关函数都定义在这里）

真正的函数实现则位于源码 ext/standard/array.c 中：

下面我就来分析这段源码的具体实现：

• 1、先对传入参数进行必要的检验和转换；
• 2、再通过 php_get_data_compare_func 设置比较函数（想想PHP某些数组排序函数支持自定义排序函数，其实所有排序函数的实现原理都是一样的，只不过这里指定了一个默认实现）；
• 3、最后通过 zend_hash_sort 进行排序操作

如果你对 C 语言不熟，还看不懂具体的代码实现，没关系，你只需要知道这个大致的流程就好了，我们重点关注最核心的步骤 zend_hash_sort 的内部实现。

我们追溯 zend_hash_sort 函数的定义，可以看到该函数定义在 Zend/zend_hash.h 头文件中：

#define zend_hash_sort(ht, compare_func, renumber) \
zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)

这是一个宏定义，你可以将其看作一个别名，当调用 zend_hash_sort(ht, compare_func, renumber) 时实际调用的是 zend_hash_sort_ex(ht, zend_sort, compare_func, renumber) 函数，这里我们可以看到两个函数对比后者新增了一个参数 zend_sort，该参数是一个函数指针，指向了真正的排序实现函数，位于 Zend/zend_sort.c 中的 zend_sort 函数：

查看 zend_sort 函数的源码，可以看到当数据量较小时（小于等于16)，会使用插入排序，因为此时插入排序性能更好；否则会使用快速排序。

感兴趣的同学，可以以此为例查看其他数组排序函数的底层实现，如 asort、ksort、usort 等。