如何轻松理解排序函数

这是我自最早接触 Javascript 的排序之日起一直萦绕在脑海中的问题。比如一个简单的 Javascript 数组排序

[3, 2, 4, 6, 5].sort(function(e1, e2) {
    return e1 - e2;
});

当然我那时候还不会用 JSON 和无名函数来写上面的代码。 反正经常是搞不清楚想要升序或降序时,是应该 return e1 - e2 还是 return e2 - e1 ?,没把握就试一下,总是二选一。

现在许多语言对集合排序都是使用排序函数的方式,总不想每次都琢磨不定,每次都去试。需要 TDD 时测试用例必须覆盖排序用例,但还是希望以后书写排序函数时心里有个底。当然,比如在 Java 中对集合进行排序我们可以深入到源代码来理解排序函数是如何影响元素顺序的。

简单通俗点,是否有一种浅显的方式来理解排序函数呢?待我把答案慢慢叙来,就我个人理解就两个原则:

  1. 排序过程总是试图把元素整理成自然顺序,即由小及大
  2. 排序函数返回值对应及相应操作:
    1. 正数: 逻辑上认为前面的比后面的大,按照自然顺序需交换位置
    2. 零: 相等,不影响排序
    3. 负数: 逻辑上认为前面的比后面的小,符合由小及大的关系,无需交换位置

既然排序函数返回零或负数时无需调整元素顺序,所以我们把关注点落在什么情况下要交换元素顺序。回到最前面的例子,对于元素 3 和 2 时

function(e1, e2) { return e1 - e2 } 返回的是正数,就说明逻辑上 e1 比 e2 大,需要交换位置,即把 3, 2 变为 2, 3, 按这样的规则排序后就是 [2, 3, 4, 5, 6] 这样的顺序。

如果 function(e1, e2) { return e2 - e1 } 呢,它返回的是负数,说明符合升序的逻辑,无需交换位置,即还是 3, 2,如此排序后便是 [6, 5, 4, 3, 2] 的顺序。

刚刚头脑中好像还有点清晰,现在反而又迷糊了。

其实排序函数对于排序的干预我们只需关心返回值是正数还是非正数(零或负数)

或者我们换一种思维,我们要实现排序后的终极目标是: 完成排序后,依次抽两个元素来调用排序函数, 返回必须是零或负数, 即 e1 - e2 是零或负数。也就是符合了逻辑上由小及大的顺序。

期待有更合理的理解......

本文链接 https://yanbin.blog/understand-sort-function/, 来自 隔叶黄莺 Yanbin Blog

[版权声明] Creative Commons License 本文采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 进行许可。

Subscribe
Notify of
guest

1 Comment
Inline Feedbacks
View all comments
李阳博客
李阳博客
8 years ago

过来学习大神的杰作