摘要:在算法中,比快速排序还快的,无疑是基数排序,粗略看了一下算法,可能是基础排序中的桶排序。桶排序是稳定的桶排序是常见排序里最快的一种,比快排还要快大多数情况下桶排序非常快,但是同时也非常耗空间以空间换时间
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桶排序。
桶排序是稳定的
桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
桶排序非常快,但是同时也非常耗空间(以空间换时间)
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/20608.html
摘要:良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法,被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止,我们已经看到了两种基于比较的排序算法。 预警 本文适合对于排序算法不太了解的新手同学观看,大佬直接忽略即可。因为考虑到连贯性,所以篇幅较长。老铁们看完需要大概一个小时,但是从入门到完全理解可能需要10个小时(哈哈哈,以我自己...
摘要:排序严格来说不算数据结构,更应该归于算法一类,因为数据结构指的是数据与数据之间的关系,排序参与其中,更多的是让数据状态发生了改变。 排序严格来说不算数据结构,更应该归于算法一类,因为数据结构指的是数据与数据之间的关系,排序参与其中,更多的是让数据状态发生了改变。于是,我们开始用PHP来聊聊算法。 引子 其实有一句话说的是不错的,不必重复造轮子,所以下面我将引用别人的文章作为本文的引文,...
阅读 3525·2021-10-09 09:43
阅读 6120·2021-09-07 10:15
阅读 2731·2019-08-30 14:03
阅读 3058·2019-08-29 11:01
阅读 1694·2019-08-29 10:56
阅读 1060·2019-08-28 17:52
阅读 3482·2019-08-26 11:42
阅读 2531·2019-08-26 10:33