如何优雅的构建排序公式

<div class="iteye-blog-content-contain" style="font-size: 14px"></div>

最近的一个项目中的需求要对一堆元素进行排序，排序的依据是元素在页面上面的坐标位置，然后按照顺序给所有元素一个编号。如下图所示：

 

排序并编号

做这个需求的是一个新入职的小伙，思考摸索了很久，他也没有找到合适的方法。不得不说，部分新入职的小伙的思维能力还是有待提高啊。其实这个问题很简单，就是对元素按照坐标进行排序。从图上可以看出规则是x坐标优先于y坐标，具体来说，两个元素a和b：
如果a.x > b.x 则 a > b,
如果a.x < b.x 则 a < b,
如果a.x = b.x ，则当a.y > b.y时 a > b，a.y < b.y时候，a < b

把上面的规则翻译成JavaScript，并结合数组排序函数，很轻松就得出了解决方案：

array.sort(function(a,b){
   if(a.x > b.x ){
        return 1;
    }else if (a.x < b.x ){
        return - 1;
    }
    return a.y - b.y
})

以上规则 还可以整理成这样一句话，就是： 当x坐标相同时，用y坐标作为排序依据，单x坐标不同时，用x坐标作为排序依据，翻译成代码如下

array.sort(function(a,b){
   if(a.x  !=  b.x ){
        return a.x - b.x
    }else {
        return a.y - b.y
    }
})

改成三元运算符就是：

array.sort(function(a,b){
        return (a.x  !=  b.x) ? (a.x - b.x) : (a.y - b.y)
})

排序公式

上面已经解决了问题中的需求，但是有没有一个数学公式就可以解决这个问题呢？ 为什么要想数学公式，因为数学公式是对于世间事物最好的、最优雅的提炼。
经过思考，可以考虑把x坐标的差值的单位值和y坐标的差值的单位值，通过一定的加权比例相加，由于x要占用的比例更高，所以考虑x的加权值更大，公式如下：

Math.sign(a.x - b.x) * 2 + Math.sign(a.y - b.y)
当a.x == b.x的时候，Math.sign(a.x - b.x) == 0，应此判断的依据自然是y坐标。
当a.x != b.x的时候,Math.sign(a.x - b.x) * 2的值为 2 或者 -2 ， Math.sign(a.y - b.y) 的值 为1或者0，或者-1，所以相加的结果的正负是由Math.sign(a.x - b.x) * 2决定，也就是x坐标决定。
最终通过这个数学，改进代码如下：

array.sort(function(a,b){
        return Math.sign(a.x - b.x) * 2  + Math.sign(a.y - b.y) 
})

三维坐标排序和N维坐标排序

如果是三维坐标（x,y,z) 排序，x优先，y次之，z最末。 那么如果是用if判断，代码应该如下：

array.sort(function(a,b){
        return (a.x  !=  b.x) ? (a.x - b.x) :（ (a.y != b.y) ?   (a.y - b.y) : (a.z - b.z)
})

x如果不相等，以x差值为判断依据，x如果相等，如果y不相等，以y差值作为判断依据，否则 以z值差值作为判断依据。
如果同样要构建一个数学工具呢？思路和前面一样，把x坐标的差值的单位值和y坐标的差值的单位值以及z坐标的差值的单位值，通过一定的加权比例相加，由于x要占用的比例更高，所以考虑x的加权值更大，y要次之。如何来分配权值呢？ 因为不能只是x的权值比y的大，其实应该是x的权值比y和z的权值之和都要打，我最开始想的是这样的：

Math.sign(a.x - b.x) * 100 + Math.sign(a.y - b.y) * 10 + Math.sign(a.z - b.z)

不过很快我否决了，用100和10可以满足要求，但是感觉这个差值太多，没有必要，
突然想到2的幂有一个公式，就是：

1 + 22 +... + 2n-1 = 2n - 1

可以看出 2n大于1 + 22 +... + 2n-1之和，应此可以使用如下公式：

Math.sign(a.x - b.x) * 4 + Math.sign(a.y - b.y) * 2 + Math.sign(a.z - b.z)

根据这个公式，如果是n维向量的排序，大概如下：

Math.sign(a.x1 - b.x1) * Math.pow(2,n) + Math.sign(a.x2 - b.x2) * Math.pow(2,n-1) + ... + Math.sign(a.xn - b.xn) * 1

后记

可能有人会说，我直接用条件判断也可以做出来，你这个公式有什么用？ 其实我前面说了，因为数学公式是对于世间事物最好的、最优雅的提炼。
同时这也是一个有意思的思考练习，相信可以培养你的思维能力。 很多时候，多想想并没有错，虽然暂时看起来没有太多作用。

欢迎关注公众号“ITman彪叔”。彪叔，拥有10多年开发经验，现任公司系统架构师、技术总监、技术培训师、职业规划师。熟悉Java、JavaScript、Python语言，熟悉数据库。熟悉java、nodejs应用系统架构，大数据高并发、高可用、分布式架构。在计算机图形学、WebGL、前端可视化方面有深入研究。对程序员思维能力训练和培训、程序员职业规划有浓厚兴趣。

 

ITman彪叔公众号