首先查看asort函數(shù)先找到其實(shí)現(xiàn)文件，PHP的源碼中所有的標(biāo)準(zhǔn)庫(kù)函數(shù)都定義在ext/standard目錄中,asort其功能為array所使用，所以我們?cè)赼rray.c中果然找到了此方法的實(shí)現(xiàn)

PHP_FUNCTION(asort)
{
    zval *array;
    zend_long sort_type = PHP_SORT_REGULAR;
    compare_func_t cmp;

    if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
        RETURN_FALSE;
    }

    cmp = php_get_data_compare_func(sort_type, 0);

    if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
        RETURN_FALSE;
    }
    RETURN_TRUE;
}

• 首先定義了zval實(shí)現(xiàn)的array指針，并定義了sort_type為PHP_SORT_REGULAR，這個(gè)變量在后面比較類型判斷的時(shí)候使用；
• 又調(diào)用了zend_parse_parameters，這個(gè)函數(shù)就不在這里解析了，這個(gè)函數(shù)的實(shí)現(xiàn)結(jié)果是獲取調(diào)用函數(shù)的傳入?yún)?shù)，第一個(gè)參數(shù)是array,也就是我們需要排序的數(shù)組地址，我們可以看到其實(shí)有個(gè)傳入?yún)?shù)sort_type，這里需要注意下這個(gè)傳入?yún)?shù).
• 接下來(lái)就是php_get_data_compare_func，這個(gè)函數(shù)是用作根據(jù)傳入的sort_type來(lái)獲取要使用的比較方法，我們來(lái)分析下這個(gè)方法

static compare_func_t php_get_data_compare_func(zend_long sort_type, int reverse) /* {{{ */
{
    switch (sort_type & ~PHP_SORT_FLAG_CASE) {
        case PHP_SORT_NUMERIC:
            if (reverse) {
                return php_array_reverse_data_compare_numeric;
            } else {
                return php_array_data_compare_numeric;
            }
            break;

        case PHP_SORT_STRING:
            if (sort_type & PHP_SORT_FLAG_CASE) {
                if (reverse) {
                    return php_array_reverse_data_compare_string_case;
                } else {
                    return php_array_data_compare_string_case;
                }
            } else {
                if (reverse) {
                    return php_array_reverse_data_compare_string;
                } else {
                    return php_array_data_compare_string;
                }
            }
            break;

        case PHP_SORT_NATURAL:
            if (sort_type & PHP_SORT_FLAG_CASE) {
                if (reverse) {
                    return php_array_reverse_natural_case_compare;
                } else {
                    return php_array_natural_case_compare;
                }
            } else {
                if (reverse) {
                    return php_array_reverse_natural_compare;
                } else {
                    return php_array_natural_compare;
                }
            }
            break;

#if HAVE_STRCOLL
        case PHP_SORT_LOCALE_STRING:
            if (reverse) {
                return php_array_reverse_data_compare_string_locale;
            } else {
                return php_array_data_compare_string_locale;
            }
            break;
#endif

        case PHP_SORT_REGULAR:
        default:
            if (reverse) {
                return php_array_reverse_data_compare;
            } else {
                return php_array_data_compare;
            }
            break;
    }
    return NULL;
}

此篇文章我們只比較常規(guī)情況下PHP_SORT_REGULAR類型下的復(fù)雜度

• 如上函數(shù)實(shí)現(xiàn)，我們可以看到我們asort情況也就是升序下調(diào)用的是php_array_data_compare,如果是arsort降序下是php_array_reverse_data_compare。

    cmp = php_get_data_compare_func(sort_type, 0);
    if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
        RETURN_FALSE;
    }

此時(shí)已經(jīng)返回了我們要使用的比較函數(shù)，接下來(lái)就是調(diào)用zend_hash_sort進(jìn)行最終的處理了
zend_hash_sort定義肯定就要去zend目錄進(jìn)行查看了，此函數(shù)定義在zend_hash.h文件中

#define zend_hash_sort(ht, compare_func, renumber) \
    zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)

可以看到h文件中定義了zend_hash_sort為zend_hash_sort_ex的實(shí)現(xiàn)，所以我們跟蹤zend_hash_sort_ex，查看zend_hash.c文件，找到zend_hash_sort_ex的實(shí)現(xiàn)

ZEND_API int ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, compare_func_t compar, zend_bool renumber)
{
    Bucket *p;
    uint32_t i, j;

    IS_CONSISTENT(ht);
    HT_ASSERT(GC_REFCOUNT(ht) == 1);

    if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
        return SUCCESS;
    }

    if (ht->nNumUsed == ht->nNumOfElements) {
        i = ht->nNumUsed;
    } else {
        for (j = 0, i = 0; j < ht->nNumUsed; j++) {
            p = ht->arData + j;
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue;
            if (i != j) {
                ht->arData[i] = *p;
            }
            i++;
        }
    }

    sort((void *)ht->arData, i, sizeof(Bucket), compar,
            (swap_func_t)(renumber? zend_hash_bucket_renum_swap :
                ((ht->u.flags & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));

    HANDLE_BLOCK_INTERRUPTIONS();
    ht->nNumUsed = i;
    ht->nInternalPointer = 0;

    if (renumber) {
        for (j = 0; j < i; j++) {
            p = ht->arData + j;
            p->h = j;
            if (p->key) {
                zend_string_release(p->key);
                p->key = NULL;
            }
        }

        ht->nNextFreeElement = i;
    }
    if (ht->u.flags & HASH_FLAG_PACKED) {
        if (!renumber) {
            zend_hash_packed_to_hash(ht);
        }
    } else {
        if (renumber) {
            void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
            Bucket *old_buckets = ht->arData;

            new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), (ht->u.flags & HASH_FLAG_PERSISTENT));
            ht->u.flags |= HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
            ht->nTableMask = HT_MIN_MASK;
            HT_SET_DATA_ADDR(ht, new_data);
            memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
            pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT & HASH_FLAG_PERSISTENT);
            HT_HASH_RESET_PACKED(ht);
        } else {
            zend_hash_rehash(ht);
        }
    }

    HANDLE_UNBLOCK_INTERRUPTIONS();

    return SUCCESS;
}

我們只分析此實(shí)現(xiàn)中最重要的一句

sort((void *)ht->arData, i, sizeof(Bucket), compar,
            (swap_func_t)(renumber? zend_hash_bucket_renum_swap :
                ((ht->u.flags & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));

我們可以看到這里使用sort去進(jìn)行排序，sort為此函數(shù)體中第二個(gè)傳入的參數(shù),sort就是在h文件中傳入的zend_sort,我們進(jìn)入zend_sort(zend_sort.c定義)進(jìn)行分析

ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
{
    while (1) {
        if (nmemb <= 16) {
            zend_insert_sort(base, nmemb, siz, cmp, swp);
            return;
        } else {
            char *i, *j;
            char *start = (char *)base;
            char *end = start + (nmemb * siz);
            size_t offset = (nmemb >> Z_L(1));
            char *pivot = start + (offset * siz);

            if ((nmemb >> Z_L(10))) {
                size_t delta = (offset >> Z_L(1)) * siz;
                zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
            } else {
                zend_sort_3(start, pivot, end - siz, cmp, swp);
            }
            swp(start + siz, pivot);
            pivot = start + siz;
            i = pivot + siz;
            j = end - siz;
            while (1) {
                while (cmp(pivot, i) > 0) {
                    i += siz;
                    if (UNEXPECTED(i == j)) {
                        goto done;
                    }
                }
                j -= siz;
                if (UNEXPECTED(j == i)) {
                    goto done;
                }
                while (cmp(j, pivot) > 0) {
                    j -= siz;
                    if (UNEXPECTED(j == i)) {
                        goto done;
                    }
                }
                swp(i, j);
                i += siz;
                if (UNEXPECTED(i == j)) {
                    goto done;
                }
            }
done:
            swp(pivot, i - siz);
            if ((i - siz) - start < end - i) {
                zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
                base = i;
                nmemb = (end - i)/siz;
            } else {
                zend_sort(i, (end - i)/siz, siz, cmp, swp);
                nmemb = (i - start)/siz - 1;
            }
        }
    }
}

• 4-7行進(jìn)行了判斷， 如果元素總數(shù) <= 16 ，則進(jìn)行插入排序，這是很正常的，因?yàn)椴迦肱判蛟谧詈玫那闆r下時(shí)O(n) 級(jí)的算法，而數(shù)據(jù)量小的情況下，數(shù)據(jù)有序的可能性就越高，也就符合了最好的情況
• 后面就是 如果元素總數(shù) > 16， 則開(kāi)始了另外一種排序，首先確定了頭元素和尾元素，并讓元素總數(shù)右移一位作為基準(zhǔn)， 這里涉及一個(gè)函數(shù) Z_L ，后面做補(bǔ)充解釋
• 繼續(xù)判斷 nmemb >> Z_L(10) 如果 元素總數(shù) 右移 10位，依然大于 0的話，選取的偏移數(shù) 再向右偏移 1位 作為 delta， 然后 zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp); 進(jìn)行交換，否則 執(zhí)行 zend_sort_3(start, pivot, end - siz, cmp, swp); 執(zhí)行排序
• 下面就是標(biāo)準(zhǔn)的快速排序的操作思路了，只是一般我們會(huì)使用遞歸來(lái)處理，但是遞歸會(huì)消耗空間，所以 PHP源碼里面選擇了非遞歸的方式
  最后看一下zend_sort_3的實(shí)現(xiàn)

static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
    if (!(cmp(a, b) > 0)) {
        if (!(cmp(b, c) > 0)) {
            return;
        }
        swp(b, c);
        if (cmp(a, b) > 0) {
            swp(a, b);
        }
        return;
    }
    if (!(cmp(c, b) > 0)) {
        swp(a, c);
        return;
    }
    swp(a, b);
    if (cmp(b, c) > 0) {
        swp(b, c);
    }
}

總結(jié)

php的asort函數(shù)在元素?cái)?shù) 較小(16個(gè)及以下)的時(shí)候，使用插入排序，否則使用非遞歸的快速排序來(lái)進(jìn)行排序