如何使用DOM方法可靠地对数组进行子类化？

Question

UP-FRONT注意:我没有在这里使用jQuery或其他库,因为我想了解我写的是什么以及为什么它可以工作(或不工作),所以请不要用图书馆的库或插件来回答这个问题.我没有反对库,但对于这个项目,它们对我的编程目标不利.

那说......

在http://meyerweb.com/eric/css/colors/上我添加了一些使用我自己编写的DOM函数的列排序.问题是,虽然它对于字母串字符串的简单情况很有用,但当我尝试对多个数字项进行排序时,结果在浏览器中不一致 - 实际上,当我尝试使用两个子排序进行排序时.

例如,如果您在OS X上的Safari或Firefox中单击"十进制RGB"几次,您将获得我想要的结果.在Chrome或Opera(再次,OS X)中执行相同操作,您会得到截然不同的结果.是的,Safari和Chrome在这里有所不同.

这是我用于RGB排序的JS的片段:

sorter.sort(function(a,b){
    return a.blue - b.blue;
});
sorter.sort(function(a,b){
    return a.green - b.green;
});
sorter.sort(function(a,b){
    return a.red - b.red;
});

(sorter作为我正在尝试排序的数组.)

排序是在另一个StackOverflow问题的传统中完成的" 如何通过JavaScript中的多列对多维数组进行排序？" 及其最佳答案.然而,结果并不是我最初尝试的四种浏览器中的两种.

得到(ha!)得到这与数组排序"不稳定"有关 - 这里没有参数! - 但我不知道的是如何以一致,可靠的方式克服它.我真的可以使用一些帮助来理解问题和看到解决方案,或者至少是解决方案的一般描述.

我意识到可能有六百万种方法来优化JS的其余部分(是的,我使用了全局).我仍然是一个JS新手,并试图通过练习纠正它.现在,它的数组排序让我感到困惑,我可以使用该脚本的一些帮助,然后继续清理其他地方的代码.提前致谢!

UPDATE

除了下面的重要解释和建议外,我还得到了一个更紧凑的解决方案:

function rgbSort(a,b) {
    return (a.red - b.red || a.green - b.green || a.blue - b.blue);
}

即使我还不太了解它,我想我已经开始掌握它的轮廓,这就是我现在正在使用的.感谢大家的帮助!

Answer 1

好.因此,正如您所发现的,您的问题是默认的JavaScript排序不能保证稳定.具体来说,我认为在你的脑海中它的工作原理如下:我将按蓝色排序,然后当我按绿色排序时,分拣机只会上下移动我的阵列中的条目,但按蓝色排序.可悲的是,宇宙不是那么方便的安排; 内置的JS排序允许按照自己喜欢的方式进行排序.特别是,它允许将数组的内容放入一个大桶中,然后根据您的要求将它们拉出来,完全忽略它之前的排列方式,看起来至少有些浏览器正是这样做的.

对于您的特定示例,有几种方法可以解决这个问题.首先,您仍然可以在三个单独的调用中进行排序,但要确保这些调用稳定排序:这意味着在按蓝色排序后,您将按绿色稳定排序,这将为您提供按绿色排序的数组在其中的蓝色顺序(即,正是您正在寻找的).我的sorttable库通过实现"shaker sort"或"cocktail sort"方法来实现这一点(http://en.wikipedia.org/wiki/Cocktail_sort); 实质上,这种排序方式遍历列表并上下移动项目.(特别是,它没有做的只是将所有列表项放入存储桶并按顺序将它们拉出来.)维基百科文章中有一个很好的小图形.这意味着"子排序"保持排序 - 即,排序是稳定的,这将给你你想要的.

但是,对于这个用例,我不会担心在三个不同的调用中进行排序并确保它们是稳定的并且所有这些; 相反,我会一次性完成所有的排序.我们可以认为一个rgb颜色指示器(255,192,80)实际上是一个奇怪的基础中的一个大数字:为了避免太多的数学,想象它在1000基数(如果这句话没有意义,忽略它;只是想想这将整个rgb属性转换为包含所有这些属性的一个数字,有点像CSS如何计算级联中的优先级).所以这个数字可以被认为实际上是255,192,080.如果你为每一行计算这个数字,然后按这个数字排序,它就会全部解决,你只需要进行一次排序:所以不要做三种排序,你可以做一次:sorter.sort(function(a,b) { return (a.red*1000000 + a.green*1000 + a.blue) - (b.red*1000000 + b.green*1000 + b.blue) }它一切顺利.

从技术上讲,这效率稍低,因为每次调用sort函数时都必须计算"基数1000",这可能(很可能是)每行多次.如果这是一个大问题(你可以通过基准测试来解决),那么你可以使用Schwartzian变换(对不起这里的所有流行语):基本上,你为每行计算一次base-1000-number,把它们放好全部在列表中,对列表进行排序,然后浏览排序列表.因此,创建一个看起来像的列表[ [255192080, <table row 1>], [255255255, <table row 2>], [192000000, <table row 3>] ],对列表进行排序(使用类似的函数mylist.sort(function(a,b) { return a[0]-b[0]; })),然后遍历该列表并将每个s的appendChild追加到表中,这将按顺序对整个表进行排序.你可能不需要这个最后一段用于你所拥有的表,但它可能是有用的,并且知道这个技巧,sorttable.js也使用它肯定没有坏处.