PHP sort 源码
目录
ext/standard/array.c
|
|
接下来找 zend_hash_sort 。
Zend/zend_hash.h
|
|
用于排序的算法是 zend_sort 。
Zend/zend_sort.c
|
|
该排序算法来自于 LLVM 项目的 libc++ 实现。
https://github.com/llvm/llvm-project/blob/master/libcxx/include/algorithm
|
|
快排
快排是实践中最快的已知排序算法。平均时间复杂度是 O(N log N),平均空间复杂度是 O(log N)。
空间复杂度主要是递归使用的栈空间。最优递归深度是 log N 。
思路:
在数组中选一个元素作为中心元素,把数组元素划分为小于中心元素的集合以及大于中心元素的集合,两个集合放到中心元素的两边。然后再对两个集合分别划分,一直划分到元素个数为 1 或 0 的时候才停下。
优化:
- 小数组
元素较少(N <= 20)时,快排不如插入排序。使用插入排序可以节约大约 15% 的运行时间。就算有很多元素,经过不断的划分,总会有元素个数小于等于 20 的时候。
- 中心元素的选取
- 选最左边或者最右边是最简单的,但是很容易导致花费很多时间。例如数组已经有序的情况下。
- 随机选取会更好一些,但随机数的生成也比较耗时。
- 三数中值。取左、中、右位置的三个值,取中数作为中心元素。这是最好的选择,节约快排大约 5% 的运行时间。
zend_sort 是怎么做的?
元素小于等于 16 个的时候,使用插入排序
1 2 3 4
if (nmemb <= 16) { zend_insert_sort(base, nmemb, siz, cmp, swp); return; }
元素大于 16 个的时候,使用快排的指针交换法
左右两个指针分别往中间移动,直到左边指针指向大于中心元素,右边指针小于中心元素,然后左右指针值互换,再继续移动。
还有一种是挖坑法。中心元素的选取根据元素个数分为两种情况:
- 个数小于 1024 时,将数组做一次平分,取中间数和两边缘数,如
|...|...|
的竖线部分,然后取三数中值。 - 个数大于等于 1024 时,将数组做两次平分,取三个中间数和两边缘数,如
|...|...|...|...|
的竖线部分,然后取五数中值。
个数非常大时,可能会因为划分后元素个数仍大于 1024 而再取五数中值。
- 个数小于 1024 时,将数组做一次平分,取中间数和两边缘数,如