关于写一个排序函数需要注意的
基本原则
当你想写一个排序函数用在ListView_SortItems这样的方法中,或者写一些小玩意来实现IComparer的时候,需要注意排序函数需要遵循以下几个基本原则:
> 反身性:Compare(a, a) = 0
> 反对称性:Compare(a, b)必须完全和Compare(b, a)符号相反,其中,0值的符号取反被认为是0本身。
> 传递性:如果Compare(a, b) ≤ 0,并且Compare(b, c) ≤ 0,则Compare(a, c) ≤ 0。
扩展原则
下面是这几个基本原则的几个逻辑推导,前面两个比较容易理解,但是第三个可能理解起来可能要花些功夫。
> 等效可传递性:如果Compare(a, b) = 0,并且Compare(b, c) = 0,则Compare(a, c) = 0。
> 非等效可传递性:如果Compare(a, b) < 0,并且Compare(b, c) < 0,则Compare(a, c) < 0。
> 可置换性:如果Compare(a, b) = 0,则Compare(a, c)和Compare(b, c)的计算结果的符号相同。
在上面的三条基本原则中,前两个一般不容易出错,但是如果你尝试在实现排序函数时耍一些小聪明的话,则第三条原则就很容易出错。
一方面而言,这些原则要求你必须实现一个完整的顺序判断。如果你仅仅实现的是部分的顺序,则你必须以一种某种连续性的方式来将部分顺序扩展为完整顺序。
实际的一个例子
我就碰到过这么档子事儿,一位开发者想对一组任务编写排序函数,这些任务中,有些任务是其他任务的先决条件。排序函数的主要算法流程如下:
> 如果任务a是任务b的先决条件(通过某种中间任务链),则a < b。
> 如果任务b是任务a的先决条件(通过某种中间任务链),则a > b。
> 否则,a = b。因为任务不是其他任务的先决条件,所以我们不需要关心它们所处于的位置顺序。
看起来不错。
使用上面的这个排序函数,应该可以将所有任务进行某种方式的排序,并且所有的任务的先决任务都会排在前面。
实际上并不是这样。使用这个排序函数的结果就是所有的任务都杂乱无章的混在一起,不会有任何所谓的先决任务排在前面。到底是哪里出错了呢?
考虑下面的任务依赖图:
a —-> b
c
任务a是任务b的先决条件,任务c和它们之间没有任何关联。如果你使用上面的算法,则会产生”a = c”和”b = c”(因为c和a或者b之间没有任何关联),进而得出”a = b”,但这显然和实际的情况(a是任务b的先决条件)是相矛盾的。
如果你的排序函数不是完整的,则排序函数执行的结果将不会是预期的。
总结
当你写一个比较函数时,你需要确切地知道排序的元素之间的大小关系。
不要仅仅因为不知道元素是”大”还是”小”,而认为这两个元素是相等的。
- 下一篇: 从一次错误拼写所想到的
- 上一篇: 关于那些魔术般的名字(NUL, CON, PRN…)
相关推荐
- 实战经验:权限问题导致的WordPress更新失败
- Posted on 08月18日
- 使用Visual Studio开发C++应用:增量编译和Shell支持
- Posted on 07月12日
- 实现多次鼠标点击
- Posted on 12月01日
- QT工具将支持VS的Linux工程,大家拭目以待
- Posted on 02月23日
评论已关闭。