资讯专栏INFORMATION COLUMN

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

chanthuang / 1253人阅读

摘要:在算法中,比快速排序还快的,无疑是基数排序,粗略看了一下算法,可能是基础排序中的桶排序。桶排序是稳定的桶排序是常见排序里最快的一种,比快排还要快大多数情况下桶排序非常快,但是同时也非常耗空间以空间换时间

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

相关文章

  • PHP面试:尽可能多说出你知道排序算法

    摘要:良好的排序算法具有进行最少的比较和交换的特征。冒泡排序是一个基于比较的排序算法,被认为是效率最低的排序算法之一。现在让我们使用实现冒泡排序算法。插入排序到目前为止,我们已经看到了两种基于比较的排序算法。 预警 本文适合对于排序算法不太了解的新手同学观看,大佬直接忽略即可。因为考虑到连贯性,所以篇幅较长。老铁们看完需要大概一个小时,但是从入门到完全理解可能需要10个小时(哈哈哈,以我自己...

    objc94 评论0 收藏0
  • 利用PHP实现常用数据结构之排序(小白系列文章七)

    摘要:排序严格来说不算数据结构,更应该归于算法一类,因为数据结构指的是数据与数据之间的关系,排序参与其中,更多的是让数据状态发生了改变。 排序严格来说不算数据结构,更应该归于算法一类,因为数据结构指的是数据与数据之间的关系,排序参与其中,更多的是让数据状态发生了改变。于是,我们开始用PHP来聊聊算法。 引子 其实有一句话说的是不错的,不必重复造轮子,所以下面我将引用别人的文章作为本文的引文,...

    jayzou 评论0 收藏0

发表评论

0条评论

chanthuang

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<