原:PHP数组函数研究一:ksort函数
作者 斯人 | 发布于 2012 年 4 月 5 日
PHP PHP内核

PHP函数 ksort:

我们先来看看它在 PHP帮助文档里的解释.

bool ksort ( array &$array [, int $sort_flags ] )

对数组 按照键名排序,保留键名与数据的关联关系.成功返回true,失败返回false

可选参数 sort_flags 是改变排序的行为:

  • SORT_REGULAR – 正常比较单元(不改变类型)
  • SORT_NUMERIC – 单元被作为数字来比较
  • SORT_STRING – 单元被作为字符串来比较
  • SORT_LOCALE_STRING – 根据当前的区域(locale)设置来把单元当作字符串比较。PHP 4.4.0 和 5.0.2 新加。在 PHP 6 之前,使用了系统的区域设置,可以用 setlocale() 来改变。自 PHP 6 起,必须用 i18n_loc_set_default() 函数。

先用PHP来解释一下这个函数

'four','a'=>'one','c'=>'three','b'=>'two');
ksort($arr_data);
//输出
print_r($arr_data);
?>

上面这些代码执行结果

Array
(
a => one
b => two

c => three
[d] => four
)
明白了..然后去PHP源码里面看一下这个函数是怎么做的.

PHP_FUNCTION(krsort)
{
        zval *array;  //创建一个指向 zval结构的指针
        long sort_type = PHP_SORT_REGULAR;  //这个值等于 sort_flags  默认为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);
        //执行排序函数 zend_qsort和比较函数 php_array_reverse_key_compare
        if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_reverse_key_compare, 0 TSRMLS_CC) == FAILURE) {
                RETURN_FALSE;
        }
        RETURN_TRUE;
}

这个函数只是用来获取参数..真正的数据处理 是在 执行 zend_hash_sort..
php_set_compare_func是做什么的?
看它的定义

static void php_set_compare_func(int sort_type TSRMLS_DC) /* {{{ */
{
        switch (sort_type) {
                case PHP_SORT_NUMERIC:
                        ARRAYG(compare_func) = numeric_compare_function;
                        break;

                case PHP_SORT_STRING:
                        ARRAYG(compare_func) = string_compare_function;
                        break;

#if HAVE_STRCOLL
                case PHP_SORT_LOCALE_STRING:
                        ARRAYG(compare_func) = string_locale_compare_function;
                        break;
#endif

                case PHP_SORT_REGULAR:
                default:
                        ARRAYG(compare_func) = compare_function;
                        break;
        }
}

很简单..它只是根据
ksort获取到的 sort_type 参数来设置不同的 比较函数.
那么关键 就是 zend_hasn_sort函数了 ..
贴出它的定义 一点点分析

//第一个参数 是HashTable的指针 其实就是 ksort传过来的数据
//第二个参数是排序函数
//第三个参数是 比较函数
ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
                                                        compare_func_t compar, int renumber TSRMLS_DC)
{
        Bucket **arTmp;
        Bucket *p;
        int i, j;

        IS_CONSISTENT(ht);

                return SUCCESS;
        }
        /* Doesn't require sorting */
//如果$arr_data的元素个数小于等于1 则不需要比较 直接返回成功.
        if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) {
                return SUCCESS;
        }
//分配内存空间
        arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
        if (!arTmp) {
                return FAILURE;
        }
//头指针
        p = ht->pListHead;
        i = 0;
        //将数据拷贝到arTmp
        while (p) {
                arTmp[i] = p;
                p = p->pListNext;
                i++;
        }
       //排序函数 也就是 zend_qsort
        (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
       //生成双链表
        ht->pListTail = NULL;
        ht->pInternalPointer = ht->pListHead;

        arTmp[0]->pListLast = NULL;
        if (i > 1) {
               //让arTmp指向上一个节点的指针 指向 arTmp[1]
                arTmp[0]->pListNext = arTmp[1];
                for (j = 1; j < i-1; j++) {                        
                          //让arTmp第j个指向上一个节点的指针 指向 arTmp[j-1]                         
                         arTmp[j]->pListLast = arTmp[j-1];
                        //让arTmp第j个指向下一个节点的指针 指向 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);
        }
        return SUCCESS;
}

这个函数的作用就是
生成新的数组arTmp ,用zend_qsort排序,这个函数所有PHP数组排序函数中都用到了..
来看看zend_qsort函数,一点点分析

(*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
这是执行此代码的地方
所以 base 就是 上面我们新生成的数组arTmp,nmemb就是 i,也就是 个数,siz是大小,compare是 比较函数
这个函数用到的算法 二分法

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
{
        void           *begin_stack[QSORT_STACK_SIZE];
        void           *end_stack[QSORT_STACK_SIZE];
        register char  *begin;
        register char  *end;
        register char  *seg1;
        register char  *seg2;
        register char  *seg2p;
        register int    loop;
        uint            offset;

        begin_stack[0] = (char *) base;
        end_stack[0]   = (char *) base + ((nmemb - 1) * siz);

        for (loop = 0; loop >= 0; --loop) {
                begin = begin_stack[loop];
                end   = end_stack[loop];
                while (begin < end) {                         
                        offset = (end - begin) >> 1;
                        //排序
                        _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
                        seg1 = begin + siz;
                        seg2 = end;
                        while (1) {
                                for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
                                     seg1 += siz);

                                for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
                                     seg2 -= siz);

                                if (seg1 >= seg2)
                                        break;

                                _zend_qsort_swap(seg1, seg2, siz);

                                seg1 += siz;
                                seg2 -= siz;
                        }

                        _zend_qsort_swap(begin, seg2, siz);

                        seg2p = seg2;

                        if ((seg2p - begin)                                 if ((seg2p + siz) < end) {                                         begin_stack[loop] = seg2p + siz;                                         end_stack[loop++] = end;                                 }                                 end = seg2p - siz;                         }                         else {                                 if ((seg2p - siz) > begin) {
                                        begin_stack[loop] = begin;
                                        end_stack[loop++] = seg2p - siz;
                                }
                                begin = seg2p + siz;
                        }
                }
        }
}

zend_qsort用二分法根据不同的类型 来进行排序.

原文出处:http://www.imsiren.com/archives/188