今天发现了php有个自然排序的函数----natsort,第一次听说了原来还有一种叫做“自然排序”的算法,很好奇,官方手册(http://us.php.net/manual/en/function.natsort.php)
据官方手册还可以得到这样的结果:
img1.png img2.png img10.png img12.png
显然这很适合对类似文件名的排序。从结果看这种自然算法应该是去掉头和尾的非数字部分,然后对留下来的数字部分进行排序,究竟是不是,还是看一下php源码吧。
虽然是第一次查看php的内核代码,不过凭借多年看代码的经验,还是很容易找到这个自然排序算法的核心就是函数:strnatcmp_ex(位于ext/standard/strnatcmp.c文件中)。
return 0;
}
/* }}} */
/* {{{ strnatcmp_ex
* call in array.c: strnatcmp_ex(Z_STRVAL(first), Z_STRLEN(first), Z_STRVAL(second), Z_STRLEN(second), fold_case);
*/
PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case)
{
char ca, cb;
char const *ap, *bp;
char const *aend = a + a_len,
*bend = b + b_len;
int fractional, result;
if (a_len == 0 || b_len == 0)
return a_len - b_len;
ap = a;
bp = b;
while (1) {
ca = *ap; cb = *bp;
/* skip over leading spaces or zeros */
while (isspace((int)(unsigned char)ca) || (ca == '0' && (ap+1 < aend) && (*(ap+1)!='.')))
ca = *++ap;
while (isspace((int)(unsigned char)cb) || (cb == '0' && (bp+1 < bend) && (*(bp+1)!='.')))
cb = *++bp;
/* process run of digits */
if (isdigit((int)(unsigned char)ca) && isdigit((int)(unsigned char)cb)) {
fractional = (ca == '0' || cb == '0');
if (fractional)
result = compare_left(&ap, aend, &bp, bend);
else
result = compare_right(&ap, aend, &bp, bend);
if (result != 0)
return result;
else if (ap == aend && bp == bend)
/* End of the strings. Let caller sort them out. */
return 0;
else {
/* Keep on comparing from the current point. */
ca = *ap; cb = *bp;
}
}
if (fold_case) {
ca = toupper((int)(unsigned char)ca);
cb = toupper((int)(unsigned char)cb);
}
if (ca < cb)
return -1;
else if (ca > cb)
return +1;
++ap; ++bp;
if (ap >= aend && bp >= bend)
/* The strings compare the same. Perhaps the caller
will want to call strcmp to break the tie. */
return 0;
else if (ap >= aend)
return -1;
else if (bp >= bend)
return 1;
}
}
/* }}} */
从strnatcmp_ex函数中的:
所以,我觉得应该字符串(当前位置开始)中前面的空字符和数字前面的‘0’不会参与比较,比较的结果应该和
http://us.php.net/manual/en/function.natsort.php
http://sourcefrog.net/projects/natsort/example-out.txt
所说的一样,但是在我的php5.2.9中对于“0”的处理结果却不一样(例如“img002.png”与“img1.png”,我的理解应该是前者大于后者,不过在我的5.2.9中却是前者小于后者),原因还没想清楚,可能是5.2.9的一个bug,也可能是自己还没有理解清楚源码的意思。下次配置好环境再好好测试,好好消化~~
在array.c中有两个重要的数据结构很值得我们关注:
Bucket: http://www.phpchina.cn/bbs/viewthread.php?tid=88505
zval: http://www.laruence.com/2008/08/22/412.html