最近在工作中碰到一個(gè)挺有意思的問(wèn)題，線上輸入是一串排好序的關(guān)聯(lián)數(shù)組，經(jīng)過(guò)一系列處理后輸出的數(shù)組卻是亂序，且本地運(yùn)行無(wú)法復(fù)現(xiàn)。查看相關(guān)代碼后，最讓人在意的是這一段:

$categories = Arr::sort($categories, function ($node) {     return $node['default']; }, true);

作用是按default優(yōu)先級(jí)將元素提到前面，首先確認(rèn)了下線上的illuminate/support版本和本地一致，查看Arr::sort()源碼:

... $descending ? arsort($results, $options)             : asort($results, $options);

最終還是調(diào)用 php 的asort，線上是 php5 而本地和測(cè)試因?yàn)樽罱紤]升級(jí)都換成了 php7，最后在 php5 環(huán)境下成功復(fù)現(xiàn)，確定出是sort問(wèn)題。

在排序前后相等的元素相對(duì)位置不變即說(shuō)這個(gè)算法是穩(wěn)定的。

對(duì)快速排序有一定了解的話可以知道，快速排序是不穩(wěn)定的所以這段代碼在元素default優(yōu)先級(jí)都相同的情況下輸出將不會(huì)是之前的順序，但在 php7 環(huán)境下測(cè)試結(jié)果為什么會(huì)保留原來(lái)的順序呢。難道關(guān)于我之前理解的天底下所有默認(rèn)排序都是快速排序這一點(diǎn)是錯(cuò)的嗎?

好吧，讓我們來(lái)快速看看 php 源碼是如何解決這個(gè)問(wèn)題的。到 github 官方的 php-src 直接搜索asort in this repository，找c文件，找到這個(gè)函數(shù)定義在 arr.c:814

PHP_FUNCTION(asort) { 	zval *array; 	zend_long sort_type = PHP_SORT_REGULAR; 	bucket_compare_func_t cmp;  	ZEND_PARSE_PARAMETERS_START(1, 2) 		Z_PARAM_ARRAY_EX(array, 0, 1) 		Z_PARAM_OPTIONAL 		Z_PARAM_LONG(sort_type) 	ZEND_PARSE_PARAMETERS_END();  	// 設(shè)置比較函數(shù) 	cmp = php_get_data_compare_func(sort_type, 0);  	zend_hash_sort(Z_ARRVAL_P(array), cmp, 0);  	RETURN_TRUE; }

可以看到最終調(diào)用的是zend_hash_sort()，我們繼續(xù)搜索:

發(fā)現(xiàn)這個(gè)函數(shù)是zend_hash_sort_ex()的套娃，最后找到zend_hash.c:2497

ZEND_API void ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, bucket_compare_func_t compar, zend_bool renumber) { 	Bucket *p; 	uint32_t i, j;  	IS_CONSISTENT(ht); 	HT_ASSERT_RC1(ht);  	if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { 		/* Doesn't require sorting */ 		return; 	}  	// 這里的hole指數(shù)組元素被unset掉產(chǎn)生的洞 	if (HT_IS_WITHOUT_HOLES(ht)) { 		/* Store original order of elements in extra space to allow stable sorting. */ 		for (i = 0; i < ht->nNumUsed; i++) { 			Z_EXTRA(ht->arData[i].val) = i; 		} 	} else { 		/* Remove holes and store original order. */ 		for (j = 0, i = 0; j < ht->nNumUsed; j++) { 			p = ht->arData + j; 			if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue; 			if (i != j) { 				ht->arData[i] = *p; 			} 			Z_EXTRA(ht->arData[i].val) = i; 			i++; 		} 		ht->nNumUsed = i; 	}  	sort((void *)ht->arData, ht->nNumUsed, sizeof(Bucket), (compare_func_t) compar, 			(swap_func_t)(renumber? zend_hash_bucket_renum_swap : 				((HT_FLAGS(ht) & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap))); 	...

好耶！，官方注釋里就有說(shuō)明是怎么實(shí)現(xiàn)排序的穩(wěn)定性，在排序之前用這個(gè)Z_EXTRA保留了原數(shù)組元素到下標(biāo)的映射。

但當(dāng)我搜索這塊代碼提交信息時(shí)發(fā)現(xiàn)了一個(gè)問(wèn)題：穩(wěn)定排序相關(guān)的 rfc 在https://wiki.php.net/rfc/stable_sorting，可以看到是發(fā)生在今年五月份且針對(duì) php8.0 的。

?? 那之前的 php7 排序穩(wěn)定是怎么回事。

馬上構(gòu)造個(gè)例子：

$count = 10; $cc = []; for ($i=0; $i<$count; $i++) {     $cc[] = [         'id' => $i,         'default' => rand(0, 10),     ]; } $cc = Arr::sort($cc, function ($i) {    return $i['default']; }); dd($cc);

經(jīng)過(guò)多次在 php7 下的測(cè)試發(fā)現(xiàn)：當(dāng)$count比較小的時(shí)候，排序才是穩(wěn)定的，但$count較大情況下的排序又變成不穩(wěn)定。也就是線上排序不穩(wěn)定而本地?zé)o法復(fù)現(xiàn)其實(shí)是用例的數(shù)組長(zhǎng)度太短所致。

看到這里可以確定是快速排序長(zhǎng)度閾值優(yōu)化的問(wèn)題，最后查了下相關(guān)資料。php7 中的sort是基于LLVM中libc++的std::sort實(shí)現(xiàn)。當(dāng)元素?cái)?shù)量小于等于16時(shí)候有特殊優(yōu)化，大于16才走快速排序，而 php5 是直接就走快速排序的。

<?php  $count = 100; $cc = []; for ($i=0; $i<$count; $i++) {     $cc[] = [         'id' => $i,         'default' => rand(0, 10),     ]; } usort($cc, function($a, $b){     if ($a['default'] == $b['default']) return 0;     return ($a['default'] < $b['default']) ? 1 : -1; }); print_r($cc);

最后在 php8 環(huán)境下試了試，排序絕對(duì)穩(wěn)定