提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  前端

当前栏目

javascript节点排序2

JavaScript节点排序
2023-06-13 09:14:26 时间
复制代码代码如下:

//灵感来自
//http://www.cnblogs.com/jkisjk/archive/2011/01/28/array_quickly_sortby.html
varhasDuplicate=false;
varsortBy=function(nodes){
varresult=[],array=[],n=nodes.length,i=n,node;
while(node=nodes[--n]){
(array[n]=newNumber(~~node.sourceIndex))._=node;
}
array.sort(function(a,b){
if(a===b)hasDuplicate=true;
returna-b;
});
while(i)
result[--i]=array[i]._;
returnresult;
}

但标准浏览器不支持这属性，在IE中，XML文档也没有此属性，这时就需要跟据节点的parentNode与nextSibling，但如果单单是两两比较，速度是提升不了的。因此我们就转而比较最近公共祖先的孩子们的顺序了。这时，算法的威力就体现出来了。这是第一版，根据某一朋友提供的LCA搞出来的东西，当然大体思路还是归功于JK大神。但实际效果不如意，比jQuery的那个sortOrder慢，估计问题出在求LCA上。
复制代码代码如下:

//根据这里JK提供的思路
//http://www.cnblogs.com/rubylouvre/archive/2011/01/28/1947286.html#2020900
vartick=0,hasDuplicate=false;
varRage={
//formhttp://www.cnblogs.com/GrayZhang/archive/2010/12/29/find-closest-common-parent.html
getLCA:function(nodes){
varhash={},i=0,
attr="data-find"+(++tick),
length=nodes.length,
node,
parent,
counter=0,
uuid;
while(node=nodes[i++]){
parent=node;
while(parent){
if(parent.nodeType===1){
break;
}
uuid=parent.getAttribute(attr);
if(!uuid){
uuid="_"+(++counter);
parent.setAttribute(attr,uuid);
hash[uuid]={node:parent,count:1};
}else{
hash[uuid].count++;
}
parent=parent.parentNode;
}
}
for(variinhash){
if(hash[i].count===length){
returnhash[i].node;
}
}
},
getList:function(nodes,parent){//获取当前元素到最近公共祖先间的所有祖先，包括自己
varlist=[];
while(node){
if(node===parent){
break;
}
list.unshift(node);
node=node.parentNode;
}
returnlist;
},
getLists:function(){
varlists=[],getList=Rage.getList,i=0,node,list;
while(node=nodes[i++]){
list=getList(node,parent);
if(list.length){
lists[lists.length]=list;
}
}
returnlists;
},
sortList:function(a,b){
varn=Math.min(a.length,b.length),ap,bp;
for(vari=0;i<n;i++){
ap=a[i],bp=b[i]
if(ap!==bp){
while(ap=ap.nextSibling){
if(ap===bp){
return-1
}
}
return1
}
}
returna.length-b.length;
},
uniqueSort:function(nodes){
varlength=nodes.length;
varLCA=Rage.getLCA(nodes);
varlists=Rage.getLists(nodes,LCA);
lists.sort(Rage.sortList);
varlist,i=0,result=[];
while(list=lists[i++]){
result[result.length]list.pop();
}
if(result.length!==length){
result.unshift(LAC);
if(result.length!=length){
hasDuplicate=true;
}
}
returnresult;
}
}

下面是第二版，经过改进，终于比jQuery的那个快上三倍（测试对象为拥有260多个节点的文档）
复制代码代码如下:
varhasDuplicate=false;
varRage={
getList:function(node){
varlist=[];
while(node){
if(node.nodeType===9){
break;
}
list.unshift(node);
node=node.parentNode;
}
returnlist;
},
getLists:function(nodes){
varlists=[],getList=Rage.getList,i=0,node;
while(node=nodes[i++]){
lists[lists.length]=getList(node);
}
returnlists;
},
sliceList:function(lists,num){
varresult=[],i=0,list;
while(list=lists[i++]){
list=list.slice(num);
if(list.length){
result[result.length]=list;
}
}
returnresult;
},
sortList:function(a,b){
varn=Math.min(a.length,b.length),ap,bp;
for(vari=0;i<n;i++){
ap=a[i],bp=b[i]
if(ap!==bp){
while(ap=ap.nextSibling){
if(ap===bp){
return-1
}
}
return1
}
}
returna.length-b.length;
},
uniqueSort:function(nodes){
varlength=nodes.length;
varlists=Rage.getLists(nodes);
lists.sort(function(a,b){
returna.length-b.length;
});
vardepth=lists[0].length,length=lists.length,parent,cut,ii=0;
for(vari=0;i<depth;i++){
parent=lists[0][i];
cut=true;
for(varj=1;j<length;j++){
if(parent!==lists[j][i]){
cut=false;
break;
}
}
if(cut){
ii++
}else{
break;
}
}
varLCA=lists[0][ii-1];
lists=Rage.sliceList(lists,ii);
lists.sort(Rage.sortList);
varlist,i=0,result=[];
while(list=lists[i++]){
result[result.length]=list.pop();
}
if(result.length!==length){
result.unshift(LCA);
if(result.length!=length){
hasDuplicate=true;
}
}
returnresult;
}
}

相关文章