关于写一个排序函数需要注意的

关于写一个排序函数需要注意的

作者:BlogUpdater |  时间:2020-06-23 |  浏览:1338 |  评论已关闭 条评论

基本原则
当你想写一个排序函数用在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的先决条件)是相矛盾的。
如果你的排序函数不是完整的,则排序函数执行的结果将不会是预期的。

总结
当你写一个比较函数时,你需要确切地知道排序的元素之间的大小关系。
不要仅仅因为不知道元素是”大”还是”小”,而认为这两个元素是相等的。

标签:

评论已关闭。