快捷導(dǎo)航

javascript 節(jié)點排序 2

更新時間：2011年01月31日 19:02:09 作者：

對支持sourceIndex的HTML文檔的節(jié)點重排，使用JK提供的思路，速度至少比單純使用nodes.sort(function(a,b){return a.sourceIndex - b.sourceIndex})這種方式快兩倍

復(fù)制代碼代碼如下:

 
//靈感來自 
//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文檔也沒有此屬性，這時就需要跟據(jù)節(jié)點的parentNode與nextSibling，但如果單單是兩兩比較，速度是提升不了的。因此我們就轉(zhuǎn)而比較最近公共祖先的孩子們的順序了。這時，算法的威力就體現(xiàn)出來了。這是第一版，根據(jù)某一朋友提供的LCA搞出來的東西，當然大體思路還是歸功于JK大神。但實際效果不如意，比jQuery的那個sortOrder慢，估計問題出在求LCA上。

復(fù)制代碼代碼如下:

 
//根據(jù)這里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 < n; 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; 
} 
} 

下面是第二版，經(jīng)過改進，終于比jQuery的那個快上三倍（測試對象為擁有260多個節(jié)點的文檔）

復(fù)制代碼代碼如下:

 
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 < n; 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 < depth; i++){ 
parent = lists[0][i]; 
cut = true; 
for(var j = 1;j < length; 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; 
} 
} 