|
ext/standard/php_array.h
https://github.com/php/php-src/blob/master/ext/standard/php_array.h
- #ifndef PHP_ARRAY_H
- #define PHP_ARRAY_H
- PHP_MINIT_FUNCTION(array);
- PHP_MSHUTDOWN_FUNCTION(array);
- PHP_FUNCTION(ksort);
- PHP_FUNCTION(krsort);
- PHP_FUNCTION(natsort);
- PHP_FUNCTION(natcasesort);
- PHP_FUNCTION(asort);
- PHP_FUNCTION(arsort);
- PHP_FUNCTION(sort);
- PHP_FUNCTION(rsort);
- PHP_FUNCTION(usort);
- PHP_FUNCTION(uasort);
- PHP_FUNCTION(uksort);
- ……
上面定义的排序函数：
arsort -- 对数组进行逆向排序并保持索引关系
asort -- 对数组进行排序并保持索引关系
krsort -- 对数组按照键名逆向排序
ksort -- 对数组按照键名排序
natcasesort -- 用“自然排序”算法对数组进行不区分大小写字母的排序
natsort -- 用“自然排序”算法对数组排序
rsort -- 对数组逆向排序
sort -- 对数组排序
uasort -- 使用用户自定义的比较函数对数组中的值进行排序并保持索引关联
uksort -- 使用用户自定义的比较函数对数组中的键名进行排序
usort -- 使用用户自定义的比较函数对数组中的值进行排序
为了简单，只分析 sort 函数：
https://github.com/php/php-src/blob/master/ext/standard/array.c
- /* {{{ proto bool sort(array &array_arg [, int sort_flags])
- Sort an array */
- PHP_FUNCTION(sort)
- {
- zval *array;
- long sort_type = PHP_SORT_REGULAR;
- if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|l", &array, &sort_type) == FAILURE) {
- RETURN_FALSE;
- }
- php_set_compare_func(sort_type TSRMLS_CC);
- if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, 1 TSRMLS_CC) == FAILURE) {
- RETURN_FALSE;
- }
- RETURN_TRUE;
- }
- /* }}} */
在代码中，看到了
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
- (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
- HANDLE_BLOCK_INTERRUPTIONS();
- ht->pListHead = arTmp[0];
- ht->pListTail = NULL;
- ht->pInternalPointer = ht->pListHead;
- arTmp[0]->pListLast = NULL;
- if (i > 1) {
- arTmp[0]->pListNext = arTmp[1];
- for (j = 1; j < i-1; j++) {
- arTmp[j]->pListLast = arTmp[j-1];
- arTmp[j]->pListNext = arTmp[j+1];
- }
- arTmp[j]->pListLast = arTmp[j-1];
- arTmp[j]->pListNext = NULL;
- } else {
- arTmp[0]->pListNext = NULL;
- }
- ht->pListTail = arTmp[i-1];
- pefree(arTmp, ht->persistent);
- HANDLE_UNBLOCK_INTERRUPTIONS();
- if (renumber) {
- p = ht->pListHead;
- i=0;
- while (p != NULL) {
- p->nKeyLength = 0;
- p->h = i++;
- p = p->pListNext;
- }
- ht->nNextFreeElement = i;
- zend_hash_rehash(ht);
- }
在算法中，比快速排序还快的，无疑是基数排序，粗略看了一下算法，可能是基础排序中的hash桶排序。
桶排序是稳定的
桶排序是常见排序里最快的一种，比快排还要快…大多数情况下
桶排序非常快，但是同时也非常耗空间（以空间换时间） | 
