PHP 核心剖析：natsort 自然排序演算法實現原理

前言：何為自然排序？

PHP 的 natsort() 函數實現了「自然排序」演算法：按人類直覺對字母數字混合字串排序，同時保持鍵值關聯。例如檔案名 img1.png, img2.png, img10.png, img12.png，標準字串排序會產生 1, 10, 12, 2，而自然排序正確識別數值大小，產生 1, 2, 10, 12。這對檔案名、版本號等場景至關重要。

核心原始碼追蹤

入口函數 PHP_FUNCTION(natsort) 呼叫 php_natsort()，後者根據 fold_case 參數選擇比較函數，最終委派給 zend_hash_sort() 配合 zend_qsort（快速排序）執行：

static void php_natsort(INTERNAL_FUNCTION_PARAMETERS, int fold_case) {
    zval *array;
    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &array) == FAILURE) return;
    if (fold_case) {
        zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_natural_case_compare, 0 TSRMLS_CC);
    } else {
        zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_natural_compare, 0 TSRMLS_CC);
    }
    RETURN_TRUE;
}

比較函數核心：php_array_natural_general_compare()

static int php_array_natural_general_compare(const void *a, const void *b, int fold_case) {
    Bucket *f = *((Bucket **) a);
    Bucket *s = *((Bucket **) b);
    zval *fval = *((zval **) f->pData);
    zval *sval = *((zval **) s->pData);
    zval first = *fval, second = *sval;

    // 非字串轉字串（複製構造避免污染原值）
    if (Z_TYPE_P(fval) != IS_STRING) { zval_copy_ctor(&first); convert_to_string(&first); }
    if (Z_TYPE_P(sval) != IS_STRING) { zval_copy_ctor(&second); convert_to_string(&second); }

    // 核心：呼叫 strnatcmp_ex 進行自然比較
    int result = strnatcmp_ex(Z_STRVAL(first), Z_STRLEN(first), Z_STRVAL(second), Z_STRLEN(second), fold_case);

    // 清理臨時 zval
    if (Z_TYPE_P(fval) != IS_STRING) zval_dtor(&first);
    if (Z_TYPE_P(sval) != IS_STRING) zval_dtor(&second);
    return result;
}

關鍵點：

• 排序對象是 Bucket** 陣列，透過 pData 取得 zval** 再解引用獲取值。
• 非字串類型臨時轉換為字串比較，使用 zval_copy_ctor 複製構造，zval_dtor 銷毀，確保原資料不變。
• 核心演算法完全委派給 strnatcmp_ex()（位於 ext/standard/strnatcmp.c）。

strnatcmp_ex 自然比較演算法解析

該函數實現「自然順序演算法」，核心邏輯：

1. 逐字元掃描： 同步遍歷兩字串。
2. 數字片段識別： 遇到數字字元（isdigit()）時，提取連續數字子串。
3. 前導零處理： 忽略前導零比較數值大小（如 0012 vs 12 視為相等）。
4. 數值比較： 將數字子串轉為整數（或長整數）比較大小，而非字典序。
5. 非數字片段： 依 ASCII 碼或忽略大小寫（fold_case）按字典序比較。
6. 長度差異處理： 數值相同時，較短字串優先（如 1.2 < 1.20）。

簡化邏輯示意：

while (*s1 && *s2) {
    if (isdigit(*s1) && isdigit(*s2)) {
        // 提取數字段，比較數值大小
        long n1 = strtol(s1, &s1, 10);
        long n2 = strtol(s2, &s2, 10);
        if (n1 != n2) return n1 - n2;
    } else {
        // 非數字段，字元級比較
        int diff = fold_case ? toupper(*s1) - toupper(*s2) : *s1 - *s2;
        if (diff) return diff;
        s1++; s2++;
    }
}
return *s1 - *s2; // 處理長度差異

設計亮點與效能考量

• 複用 Zend 排序框架： 利用 zend_hash_sort + zend_qsort，避免重造輪子，支援任意 HashTable（陣列）。
• 比較函數解耦： 自然比較邏輯封裝於 strnatcmp_ex，可被 strnatcmp、strnatcasecmp 等複用。
• 記憶體安全： 臨時字串轉換嚴格遵循 zval 參考計數與複製構造/銷毀協議，無洩漏風險。
• 時間複雜度： 平均 O(N log N) * 比較成本。比較成本取決於字串長度與數字段數量，通常可接受。

總結

PHP 的自然排序通過 HashTable 索引陣列排序 + 快速排序 + 專用自然比較函數 三層架構實現。核心智慧集中於 strnatcmp_ex，它以線性掃描識別數字語義，打破傳統字典序限制。這一設計展示了 PHP 核心「分層委派、複用通用基礎設施」的工程哲學，也為理解 PHP 陣列操作底層機制提供了絕佳切入點。