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

2013-08-16
阅读 3 分钟
9.4k
ext/standard/php_array.h [链接] {代码...} 上面定义的排序函数: arsort -- 对数组进行逆向排序并保持索引关系 asort -- 对数组进行排序并保持索引关系 krsort -- 对数组按照键名逆向排序 ksort -- 对数组按照键名排序 natcasesort -- 用“自然排序”算法对数组进行不区分大小写字母的排序 natsort -- 用“自然排序”算法...

为什么说任何基于比较的算法将5个元素排序都需要7次?

2013-08-15
阅读 1 分钟
3.8k
排序算法对结果的唯一要求就是操作数满足全序关系: 如果 a≤b 并且 b≤c 那么 a≤c(传递性)。 对于 a 或 b,要不 a≤b,要不 b≤a(完全性)。 这个问题可以用信息论来回答。 我从 1 到 5 中挑一个数字出来让你来猜,每回合你都可以问我一个问题,我的回答“是”或“不是”(1 或 0),那么你至少需要几个回合才能保证猜出这个...