<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、前端可视化方面有深入研究。对程序员思维能力训练和培训、程序员职业规划有浓厚兴趣。
相关推荐
1、 构建二叉排序树,并进行中根序和后根序遍历 【问题描述】 构建二叉排序树,并进行中根序和后根序遍历。1,结点的权值为int型 【输入形式】 输入n个结点,其为整数 【输出形式】 二叉排序树的中根序和后根序遍历...
使用JAVA语言 构建堆, 以及堆排序、构建最优队列等
图的构建与拓扑排序
排序二叉树的基础代码,包含递归非递归二叉树构建、递归非递归遍历,获取最小最大值。
数据结构作业,平衡二叉排序树
使用 Qt 构建、C++ 作为底层开发的学生成绩管理系统,支持对学生成绩的增删改查、排序、汇总等功能.zip 使用 Qt 构建、C++ 作为底层开发的学生成绩管理系统,支持对学生成绩的增删改查、排序、汇总等功能.zip 使用 ...
如果函数足够平滑的话,在已知函数在某一点的各阶导数值的情况之下,泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的邻域中的值。泰勒公式还给出了这个多项式和实际的函数值之间的偏差。 泰勒...
选择排序,插入排序,希尔排序,堆排序,快速排序,冒泡排序,性能比较。 对于一个随机的数组,可以知道排序所需的比较次数和移动次数。用c++面向对象构建。
typedef struct node{ int data; struct node* lchild,*rchild; }* BTREE; BTREE Sort_tree(int k[],int n); void Insert(BTREE & t,int item); void INORDER(BTREE &t); int main(){ int i=0,numOfInt;...}
二叉排序树构建 (学生).c
调试了下二叉树的c语言代码,可以运行的。
根据互反判断矩阵和互补判断矩阵的转换公式 ,给出了互补判断矩阵的转换矩阵 .从最优化角度提出了互补判断矩阵排序的权的最小平方法 ,并给出了严格的理论证明 .而且 ,基于...
构建二叉排序树,对元素进行排序。数据结构算法。
mvn-build-sorter Jenkins 插件在构建队列中(重新)排序 Maven 作业 工作正在进行中
1、该资源内项目代码经过严格调试,下载即用确保可以运行! 2、该资源适合计算机相关专业(如计科、人工智能...使用 Qt 构建、C++ 作为底层开发的学生成绩管理系统源码,支持对学生成绩的增删改查、排序、汇总等功能.zip
分别构建函数,实现二叉排序树的创建,插入数据,删除结点
构建一个二叉排序树,使输入的学生信息可以按照成绩从高到低排序,放入顺序表之中,再顺序输出
堆排序是一种基于比较的排序算法,通过构建大顶堆或小顶堆来实现元素的排序。其实现原理主要包括两个步骤:首先,将待排序的序列构建成一个大顶堆(或小顶堆),此时堆顶元素即为序列的最大值(或最小值);然后,将...
C语言实现键盘输入数据构建链表后冒泡排序,工程在VS2005下编译通过并运行无误。
java基础笔记数据结构-排序二叉树,详细描述了排序二叉树的原理及其实现方式,基础数据结构。