6.4.3 节点排序与去重
为了让选择器引擎搜到的结果集尽可能接近原生 API 的结果（因为在最新的浏览器中，我们可能只使用querySelectorAll实现），我们需要让元素节点按它们在DOM树出现的顺序排序。
在IE及Opera早期的版本，我们可以使用sourceIndex进行排序。
标准浏览器可以使用 compareDocumentPosition，上面不是介绍它可以判定两个节点的位置关系吗？我们只要将它们的结果按位与4不等于0就知道其前后顺序了。
此外，标准浏览器的Range对象有一个compareBoundaryPoints方法，它也能迅速得到两个元素的前后顺序。
var compare = comparerange.compareBoundaryPoints(how, sourceRange);
compare：返回1, 0, −1（0为相等，1为comparerange在sourceRange之后，−1为comparerange在sourceRange之前）。
how：比较哪些边界点，为常数。
· Range.START_TO_START——比较两个Range节点的开始点。
· Range.END_TO_END——比较两个Range节点的结束点。
· Range.START_TO_END——用sourceRange的开始点与当前范围的结束点比较。
· Range.END_TO_START——用sourceRange的结束点与当前范围的开始点比较。
特别的情况发生于要兼容旧版本标准浏览器与XML文档时，这时只有一些很基础的DOM API，我们需要使用 nextSibling 来判定谁是“哥哥”，谁是“弟弟”。如果它们不是同一个父节点，我们就需要将问题转化为求最近公共祖先，判定谁是“父亲”，谁是“伯父”。到这里，已经是纯算法的问题了。实现的思路有许多，最直观也最笨的做法是，不断向上获取它们的父节点，直到HTML元素，连同最初的那个节点，组成两个数组，然后每次取数组最后的元素进行比较，如果相同就去掉，一直去掉到不相同为止，最后用nextSibling结束。下面是测试代码，自己找一个HTML页面做标本。
window.onload = function() {
function shuffle(a) {
//洗牌
var array = a.concat();
var i = array.length;
while (i) {
var j = Math.floor(Math.random() * i);
var t = array[--i];
array[i] = array[j];
array[j] = t;
}
return array;
}
var log = function(s) {
//查看调试消息
window.console && window.console.log(s)
}
var sliceNodes = function(arr) {
//将NodeList转换为纯数组
var ret = [],
i = arr.length;
while (i)
ret[--i] = arr[i];
return ret;
}
var sortNodes = function(a, b) {
//节点排序
var p = "parentNode",
ap = a[p],
bp = b[p];
if (a === b) {
return 0
} else if (ap === bp) {
while (a = a.nextSibling) {
if (a === b) {
return -1
}
}
return 1
} else if (!ap) {
return -1
} else if (!bp) {
return 1
}
var al = [],
ap = a
//不断往上取，一直取到HTML
while (ap && ap.nodeType === 1) {
al[al.length] = ap
ap = ap[p]
}
var bl = [],
bp = b;
while (bp && bp.nodeType === 1) {
bl[bl.length] = bp
bp = bp[p]
}
//然后逐一去掉公共祖先
ap = al.pop();
bp = bl.pop();
while (ap === bp) {
ap = al.pop();
bp = bl.pop();
}
if (ap && bp) {
while (ap = ap.nextSibling) {
if (ap === bp) {
return -1
}
}
return 1
}
return ap ? 1 : -1
}
var els = document.getElementsByTagName("*")
els = sliceNodes(els); //转换成纯数组
log(els);
els = shuffle(els); //洗牌（模拟选择器引擎最初得到的结果集的情况）
log(els);
els = els.sort(sortNodes); //进行节点排序
log(els);
}
此外，我们还有一种方法，就是选择结束后，用document.getElementsByTagName(“*”)得到所有元素节点，这时它们肯定是排好序的。我们再依次为它们添加一个类似sourceIndex的自定义属性，值为它的索引值，接下来怎么做就无需我多言了。
好了，我们暂且放下，看一下各大浏览器的实现。
Mootools的Slick引擎，它的比较函数已经注明是来自Sizzle的（准确来说Sizzle1.6左右，现在它也被改得面目全非）。
features.documentSorter = (root.compareDocumentPosition) ? function(a, b) {
if (!a.compareDocumentPosition || !b.compareDocumentPosition)
return 0;
return a.compareDocumentPosition(b) & 4 ? -1 : a === b ? 0 : 1;
} : ('sourceIndex' in root) ? function(a, b) {
if (!a.sourceIndex || !b.sourceIndex)
return 0;
return a.sourceIndex - b.sourceIndex;
} : (document.createRange) ? function(a, b) {
if (!a.ownerDocument || !b.ownerDocument)
return 0;
var aRange = a.ownerDocument.createRange(),
bRange = b.ownerDocument.createRange();
aRange.setStart(a, 0);
aRange.setEnd(a, 0);
bRange.setStart(b, 0);
bRange.setEnd(b, 0);
return aRange.compareBoundaryPoints(Range.START_TO_END, bRange);
} : null;
它没有打算支持XML与旧版本标准浏览器，不支持就不排序。
mass Framework 的 Icarus 引擎，它结合了一位编程高手 JK 给出的算法，在排序去重上远胜Sizzle。突破点在于，无论Sizzle或者Slick，它们都是通过传入比较函数进行排序。而数组的原生sort 方法，当它传一个比较函数时，不管它内部用哪种排序算法
，都需要多次比对，所以非常耗时。如果能设计让排序在不传参的情况进行，那么速度就会提高N倍！
下面是具体思路（当然只能用于IE或早期Opera）。
（1）取出元素节点的sourceIndex值，转换成一个String对象；
（2）将元素节点附在String对象上；
（3）用String对象组成数组；
（4）用原生的sort进String对象数组排序；
（5）在排好序的String数组中，按序取出元素节点，即可得到排好序的结果集。
function unique(nodes) {
if (nodes.length < 2) {
return nodes;
}
var result = [],
array = [],
uniqResult = {},
node = nodes[0],
index, ri = 0,
sourceIndex = typeof node.sourceIndex === "number",
compare = typeof node.compareDocumentPosition == "function";
//如果支持sourceIndex，我们将使用更为高效的节点排序
//http://www.cnblogs.com/jkisjk/archive/2011/01/28/array_quickly_sortby.html
if (!sourceIndex && !compare) { //用于旧版本IE的XML
var all = (node.ownerDocument || node).geElementsByTagName("*");
for (var index = 0; node = all[index]; index++) {
node.setAttribute("sourceIndex", index);
}
sourceIndex = true;
}
if (sourceIndex) { //IE opera
for (var i = 0, n = nodes.length; i < n; i++) {
node = nodes[i];
index = (node.sourceIndex || node.getAttribute("sourceIndex")) + 1e8;
if (!uniqResult[index]) { //去重
(array[ri++] = new String(index))._ = node;
uniqResult[index] = 1;
}
}
array.sort(); //排序
while (ri)
result[--ri] = array[ri]._;
return result;
} else {
nodes.sort(sortOrder); //排序
if (sortOrder.hasDuplicate) { //去重
for (i = 1; i < nodes.length; i++) {
if (nodes[i] === nodes[i - 1]) {
nodes.splice(i--, 1);
}
}
}
sortOrder.hasDuplicate = false; //还原
return nodes;
}
}
function sortOrder(a, b) {
if (a === b) {
sortOrder.hasDuplicate = true;
return 0;
} //现在标准浏览器的HTML与XML好像都支持compareDocumentPosition
if (!a.compareDocumentPosition || !b.compareDocumentPosition) {
return a.compareDocumentPosition ? -1 : 1;
}
return a.compareDocumentPosition(b) & 4 ? -1 : 1;
}