[讨论]php排序系列的函数内部的C实现是用了哪种排序算法？

ext/standard/php_array.h

https://github.com/php/php-src/blob/master/ext/standard/php_array.h

1. #ifndef PHP_ARRAY_H
2. #define PHP_ARRAY_H
4. PHP_MINIT_FUNCTION(array);
5. PHP_MSHUTDOWN_FUNCTION(array);
7. PHP_FUNCTION(ksort);
8. PHP_FUNCTION(krsort);
9. PHP_FUNCTION(natsort);
10. PHP_FUNCTION(natcasesort);
11. PHP_FUNCTION(asort);
12. PHP_FUNCTION(arsort);
13. PHP_FUNCTION(sort);
14. PHP_FUNCTION(rsort);
15. PHP_FUNCTION(usort);
16. PHP_FUNCTION(uasort);
17. PHP_FUNCTION(uksort);
18. ……

上面定义的排序函数：

为了简单，只分析 sort 函数： https://github.com/php/php-src/blob/master/ext/standard/array.c

1. /* {{{ proto bool sort(array &array_arg [, int sort_flags])
2. Sort an array */
3. PHP_FUNCTION(sort)
4. {
5. zval *array;
6. long sort_type = PHP_SORT_REGULAR;
8. if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
9. RETURN_FALSE;
10. }
12. php_set_compare_func(sort_type TSRMLS_CC);
14. if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, 1 TSRMLS_CC) == FAILURE) {
15. RETURN_FALSE;
16. }
17. RETURN_TRUE;
18. }
19. /* }}} */

在代码中，看到了

if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, ……

使用快速排序的可能性大。

继续分析。

Zend/zend_hash.c

https://github.com/php/php-src/blob/master/Zend/zend_hash.c

1. (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
3. HANDLE_BLOCK_INTERRUPTIONS();
4. ht->pListHead = arTmp[0];
5. ht->pListTail = NULL;
6. ht->pInternalPointer = ht->pListHead;
8. arTmp[0]->pListLast = NULL;
9. if (i > 1) {
10. arTmp[0]->pListNext = arTmp[1];
11. for (j = 1; j < i-1; j++) {
12. arTmp[j]->pListLast = arTmp[j-1];
13. arTmp[j]->pListNext = arTmp[j+1];
14. }
15. arTmp[j]->pListLast = arTmp[j-1];
16. arTmp[j]->pListNext = NULL;
17. } else {
18. arTmp[0]->pListNext = NULL;
19. }
20. ht->pListTail = arTmp[i-1];
22. pefree(arTmp, ht->persistent);
23. HANDLE_UNBLOCK_INTERRUPTIONS();
25. if (renumber) {
26. p = ht->pListHead;
27. i=0;
28. while (p != NULL) {
29. p->nKeyLength = 0;
30. p->h = i++;
31. p = p->pListNext;
32. }
33. ht->nNextFreeElement = i;
34. zend_hash_rehash(ht);
35. }

在算法中，比快速排序还快的，无疑是基数排序，粗略看了一下算法，可能是基础排序中的hash桶排序。