如何優雅的構建排序公式

最近的一個項目中的需求要對一堆元素進行排序，排序的依據是元素在頁面上面的坐標位置，然後按照順序給所有元素一個編號。如下圖所示：

做這個需求的是一個新入職的小伙，思考摸索了很久，他也沒有找到合適的方法。不得不說，部分新入職的小伙的思維能力還是有待提高啊。其實這個問題很簡單，就是對元素按照坐標進行排序。從圖上可以看出規則是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、前端可視化方面有深入研究。對程式員思維能力訓練和培訓、程式員職業規劃有濃厚興趣。