您好,欢迎访问一九零五行业门户网

javascript 节点排序 2_javascript技巧

复制代码 代码如下:
//灵感来自
//http://www.cnblogs.com/jkisjk/archive/2011/01/28/array_quickly_sortby.html
var hasduplicate = false;
var sortby = function(nodes){
var result = [], array = [], n = nodes.length, i = n, node;
while(node = nodes[--n]){
(array[n] = new number(~~node.sourceindex))._ = node;
}
array.sort(function(a,b){
if(a === b) hasduplicate = true;
return a - b ;
});
while( i )
result[--i] = array[i]._;
return result;
}
但标准浏览器不支持这属性,在ie中,xml文档也没有此属性,这时就需要跟据节点的parentnode与nextsibling,但如果单单是两两比较,速度是提升不了的。因此我们就转而比较最近公共祖先的孩子们的顺序了。这时,算法的威力就体现出来了。这是第一版,根据某一朋友提供的lca搞出来的东西,当然大体思路还是归功于jk大神。但实际效果不如意,比jquery的那个sortorder慢,估计问题出在求lca上。
复制代码 代码如下:
//根据这里jk提供的思路
//http://www.cnblogs.com/rubylouvre/archive/2011/01/28/1947286.html#2020900
var tick = 0, hasduplicate = false;
var rage = {
//form http://www.cnblogs.com/grayzhang/archive/2010/12/29/find-closest-common-parent.html
getlca:function(nodes){
var hash = {}, 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(var i in hash){
if(hash[i].count === length){
return hash[i].node;
}
}
},
getlist : function(nodes,parent){//获取当前元素到最近公共祖先间的所有祖先,包括自己
var list = [];
while(node){
if(node === parent){
break;
}
list.unshift(node);
node = node.parentnode;
}
return list;
},
getlists : function(){
var lists = [], getlist = rage.getlist, i=0, node, list;
while(node = nodes[i++]){
list = getlist(node,parent);
if(list.length){
lists[ lists.length ] = list;
}
}
return lists;
},
sortlist : function(a,b){
var n = math.min(a.length,b.length),ap,bp;
for(var i=0; i ap = a[i],bp = b[i]
if(ap !== bp){
while(ap = ap.nextsibling){
if(ap === bp){
return -1
}
}
return 1
}
}
return a.length-b.length;
},
uniquesort : function(nodes){
var length = nodes.length;
var lca = rage.getlca(nodes);
var lists = rage.getlists(nodes,lca);
lists.sort(rage.sortlist);
var list, 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;
}
}
return result;
}
}
下面是第二版,经过改进,终于比jquery的那个快上三倍(测试对象为拥有260多个节点的文档)
复制代码 代码如下:
var hasduplicate = false;
var rage = {
getlist : function(node){
var list = [];
while(node){
if(node.nodetype === 9){
break;
}
list.unshift(node);
node = node.parentnode;
}
return list;
},
getlists : function(nodes){
var lists = [], getlist = rage.getlist, i=0, node;
while(node = nodes[i++]){
lists[ lists.length ] = getlist(node);
}
return lists;
},
slicelist : function(lists,num){
var result = [], i = 0, list;
while(list = lists[i++]){
list = list.slice(num);
if(list.length){
result[ result.length ] = list;
}
}
return result;
},
sortlist : function(a,b){
var n = math.min(a.length,b.length),ap,bp;
for(var i=0; i ap = a[i],bp = b[i]
if(ap !== bp){
while(ap = ap.nextsibling){
if(ap === bp){
return -1
}
}
return 1
}
}
return a.length-b.length;
},
uniquesort : function(nodes){
var length = nodes.length;
var lists = rage.getlists(nodes);
lists.sort(function(a,b){
return a.length - b.length;
});
var depth = lists[0].length, length = lists.length, parent, cut, ii = 0;
for(var i =0; i parent = lists[0][i];
cut = true;
for(var j = 1;j if(parent !== lists[j][i]){
cut = false;
break;
}
}
if(cut){
ii++
}else{
break;
}
}
var lca = lists[0][ii-1];
lists = rage.slicelist(lists,ii);
lists.sort(rage.sortlist);
var list, 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;
}
}
return result;
}
}
其它类似信息

推荐信息