`
flyfox1982
  • 浏览: 81084 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

如何优雅的构建排序公式

阅读更多

<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彪叔公众号
ITman彪叔公众号
分享到:
评论

相关推荐

    C程序设计的常用算法

    - **堆排序**:基于完全二叉树的特性,构建和调整堆结构,实现排序。 **2. 查找算法** 查找算法用于在数据集合中寻找特定元素。基本的查找算法有线性查找、二分查找和哈希查找。 - **线性查找**:从头到尾逐个比较...

    C语言经典算法程序集.rar

    - **堆排序(Heap Sort)**:利用完全二叉树的特性构建最大(或最小)堆,然后交换堆顶元素与末尾元素,调整堆。 2. **查找算法**: - **线性查找(Linear Search)**:逐个检查序列中的元素,直到找到目标元素或...

    计算机程序设计艺术(中文版)pdf三卷合集

    第一卷《基本算法》介绍了程序设计的基本原理,包括数据结构、递归、分治策略等,这些是构建高效算法的基础。克努斯通过丰富的实例和严谨的数学分析,阐述了如何设计和评估算法的效率。 第二卷《半数值算法》则聚焦...

    算法导论第二版(中文,高清)+经典答案

    这些方法是解决复杂问题的关键工具,帮助程序员构建高效且优雅的代码。书中还深入探讨了数据结构,如数组、链表、栈、队列、树、图等,以及它们在算法中的应用。 在算法分析方面,《算法导论》深入浅出地介绍了时间...

    excel-manager-源码.rar

    通过对源码的分析,我们可以揭示出Excel Manager在处理大量数据时的策略和技巧,同时也能学习到如何构建一个高效、易用的数据处理工具。 首先,让我们来看看Excel Manager的核心功能。它可能包括: 1. **数据读取...

    迈进算法世界的大门

    以归并排序为例,该算法遵循分治法的思路,首先将原始数组不断分割直至每个子数组仅含单个元素,随后两两合并,逐步构建出完全排序的数组。这一过程既体现了算法的优雅,又展示了分治法在提高效率方面的显著作用。 ...

    flex 电子表格 源码

    深入源码,我们可以学习到如何利用Flex的MXML和ActionScript来创建可定制的用户界面,如何处理数据模型与视图之间的同步,以及如何优雅地处理用户交互。同时,源码中的错误处理和性能优化策略也是值得借鉴的部分,这...

    TMS Business Core Library1.12 (Wednesday, December 26, 2018).rar

    例如,TMSDataEngine组件可以帮助开发者轻松地处理数据库连接、查询、事务等操作,而TMSBusinessDBGrid则可以优雅地展示和编辑数据库中的数据,提供多列排序、分页、过滤等功能。 三、用户界面 在用户界面设计上,...

    DataStructures:包含一些用于自然对应算法,k公式以及中缀和后缀转换的脚本

    这种算法在处理序列数据时特别有用,比如对数字序列进行查找、排序或者建立索引。在实际编程中,这可能表现为一个自增的ID与数据库记录之间的映射,或者是在树结构中找到某个节点的路径。 接下来,K公式在计算机...

    Pure C solution for LeetCode.zip

    例如,"sss"文件可能包含了C语言实现的二分查找、快速排序、哈希表构建等算法,这些都是LeetCode中常见的问题类型。学习这些解决方案,你可以深入理解数据结构的内部工作原理,从而提升你的编程技巧。 其次,C语言...

    电子科技大学硕博士学位论文latex模板

    LaTeX是一种基于TeX的文字处理系统,尤其适用于科技类文档的排版,因其强大的数学公式编辑能力、自动引用管理和优雅的排版效果而受到广泛欢迎。 在使用这款模板时,学生可以快速构建出符合电子科技大学论文格式要求...

    math

    总的来说,数学是IT领域的基石,无论是在前端网页开发中优雅地展示数学公式,还是在后端进行高效算法设计,都离不开数学的支撑。因此,对于IT从业者来说,提升数学素养是提高专业技能的重要途径。通过学习和理解...

    C#基于DataGridView仿Excel

    4. 自定义行为:为了完全模拟Excel的行为,可能还需要实现其他特性,比如条件格式化(根据单元格值改变其颜色或样式)、公式计算(在单元格内使用公式计算结果)、合并单元格等。这需要对DataGridView的事件系统有...

    Xlspreadsheet1_visualbasic_VBexcel_

    7. **公式和函数**:利用Excel的内置公式和VBA函数进行数据计算和分析。 综上所述,这个项目涉及到了使用Visual Basic与Excel集成的关键技术,包括通过VBA对Excel工作簿的操作、数据的导入导出以及可能的用户界面...

    《Excel 2007 VBA实战技巧精粹》示例

    通过VBA,你可以编写程序来处理大量数据,执行数据分析,创建动态图表,甚至构建完全自定义的工作簿应用。 300个实用案例的代码资料是这个资源的核心部分。这些案例涵盖了从简单的数据操作到复杂的工作流集成,它们...

    韩国矢量花纹模板

    这些矢量花纹模板以其精细的线条、优雅的图案和独特的色彩搭配,展示了韩国传统与现代美学的结合,能够为网页增添独特的视觉魅力。 矢量图形是基于数学公式和路径来描述图像的,而非像素点,因此具有可无限缩放不...

    提取文件名并保存至Excel

    8. **数据整理**:在Excel中,可以使用公式、排序和过滤等功能进一步处理和分析这些文件名。例如,可以找出所有以特定字符串开头或结尾的文件,或者统计不同类型的文件数量。 9. **可视化**:如果需要,还可以使用...

    基于Excel VBA技术的高校工资业务自动化辅助工具设计与应用.rar

    通过VBA,我们可以构建自动化工具来简化这些任务,提高工作效率,减少人为错误。以下是一些可能的知识点: 1. **VBA基础**:了解VBA的基础语法,包括变量声明、数据类型、控制结构(如If...Then...Else,For...Next...

    算法基础《C#数据结构》

    例如,通过使用Stack类,教师可以直接演示堆栈的运作机制,如数制转换,而无需从零开始构建整个数据结构,从而让学生更快地理解并应用数据结构的基本概念。 ### 泛型编程的重要性 泛型编程是C#语言的一个重要特性...

Global site tag (gtag.js) - Google Analytics