JavaScript中的排序：不应该返回一个布尔值足以用于比较函数？

本文介绍了JavaScript中的排序：不应该返回一个布尔值足以用于比较函数？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我总是成功地排序我的数组像这样（当我不想要标准的字典排序）：I have always successfully sorted my arrays like this (when I did not want the standard lexicographic ordering):var arr = […] // some numbers or soarr.sort(function(a, b) { return a > b;});现在，有人告诉我这是错误的，我需要 return ab 。是真的，如果是真的，为什么？我测试了我的比较功能，它的工作原理！此外，为什么我的解决方案在发生错误时如此常见？Now, someone told me this was wrong, and that I would need to return a-b instead. Is that true, and if yes why? I have tested my comparison function, and it works! Also, why would my solution be so common when it is wrong?推荐答案 TL; DR TL;DR不，你没有。并没有注意到。快速反例：No, you have not. And didn't notice it. A quick counterexample:> [1,1,0,2].sort(function(a, b){ return a>b })Array [0, 1, 2, 1]// in Opera 12. Results may vary between sorting algorithm implementations 因为您的比较函数会返回 false （或 0 ，等价），即使 b 大于 a 但是 0 意味着两个元素被认为是相等的 - 并且排序算法认为。Because your comparison function does return false (or 0, equivalently) even when b is larger than a. But 0 implies that the two elements are considered equal - and the sorting algorithm believes that. Array :: sort 方法可以使用可选的自定义比较函数作为其参数。该函数需要两个参数（通常称为 a 和 b ），它应该比较， 号 The Array::sort method can take an optional, custom comparison function as its argument. That function takes two arguments (commonly referred to as a and b) which it should compare, and is supposed to return a number 0 ，当 a 被认为大于 b > == 0 当 a 被视为等于 b 并不重要哪个第一 < 0 当 a 被认为小于 b > > 0 when a is considered larger than b and should be sorted after it== 0 when a is considered equal to b and it doesn't matter which comes first< 0 when a is considered smaller than b and should be sorted before it如果它不返回一个数字，结果将被转换为一个数字（这对于布尔值很方便）。返回的数字不需要完全 -1 或 0 或 1 If it does not return a number, the result will be cast to a number (which is handy for booleans). The returned number does not need to be exactly -1 or 0 or 1 (though it typically is).为了保持一致，比较函数需要满足方程To be consistent, the compare function would need to fulfill the equationcomp(a, b) == -1 * comp(b, a)// or, if values other than -1, 0 and 1 are considered:comp(a, b) * comp(b, a) <= 0如果该要求被破坏，则排序将为未定义。If that requirement is broken, the sort will behave undefined. =http://es5.github.io/#x15.4.4.11>在排序 上的ES5.1规格（ ES6 spec ）：Citing the ES5.1 spec on sort (same thing in the ES6 spec): 函数 comparefn 是一个集合的一致比较函数，， b S / code>中的和 c （可能相同的值）： c $ c> a< CF b 意味着 comparefn（a，b） 0 ; a = CF b 表示 comparefn（a，b）= 0 和 a> CF b 表示 comparefn（a，b） 0 。 A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0. 调用 comparefn（a，b）给定一个特定的值对 a 和 b 时，总是返回相同的值 v / code>作为它的两个参数。此外， Type（v）是Number， v 不是 NaN 。注意，这意味着 a ， a = CF b ，和 b a> CF b >。 Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b. 调用 comparefn（a，b）不修改此对象。 a = CF a （ reflexivity ） 如果 a = CF b ，然后 b = CF a （对称性 / code>，然后 a = CF c （传导性 = CF ） code>和 b ，则 a $ c>< CF ） 如果 a> CF b 和 b> CF c ，然后 a> CF c （ ; CF ） Calling comparefn(a,b) does not modify the this object. a =CF a (reflexivity) If a =CF b, then b =CF a (symmetry) If a =CF b and b =CF c, then a =CF c (transitivity of =CF) If a <CF b and b <CF c, then a <CF c (transitivity of <CF) If a >CF b and b >CF c, then a >CF c (transitivity of >CF) 注意：上述条件是必要的，确保 comparefn 将集合 S 划分为等价类，并且这些等价类是完全有序的。 / p> NOTE: The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered. 排序算法需要将数组的项目彼此进行比较。要做一个好的，高效的工作，它不必需要比较每个项目，每个其他，但需要能够推理他们的顺序。为了使其工作正常，有一些自定义比较函数需要遵守的规则。一个简单的一个是一个项 a 等于它自己（ compare（a，a）== 0 ） - 这是上面列表中的第一项（反身性）。是的，这是一个有点数学，但支付良好。A sorting algorithm needs to compare items of the array with each other. To do a good and efficient job, it must not need to compare each item to every other, but needs to be able to reason about their ordering. For that to work well, there are a few rules that a custom comparison function needs to abide. A trivial one is that an item a is equal to itself (compare(a, a) == 0) - that's the first item in the list above (reflexivity). Yes, this is a bit mathematical, but pays of well.最重要的是传递性。它说当算法比较两个值 a 和 b ，以及 b 与 c ，并通过应用比较函数发现eg a = b 和 b ，然后它可以期望， c 。这似乎只是合乎逻辑的，并且是一个定义良好，一致性排序所必需的。The most important one is transitivity. It says that when the algorithm has compared two values a and b, and also b with c, and has found out by applying the comparison function that e.g. a = b and b < c, then it can expect that a < c holds as well. This seems only logical, and is required for a well-defined, consistent ordering.但是你的比较函数确实失败了。让我们看看这个例子：But your comparison function does fail this. Lets look at this example: function compare(a, b) { return Number(a > b); } compare(0, 2) == 0 // ah, 2 and 0 are equal compare(1, 0) == 1 // ah, 1 is larger than 0 // let's conclude: 1 is also larger than 2这就是为什么当使用不一致的比较函数调用排序算法时，排序算法可能失败（在规范中，这是实现相关行为 - 即不可预测的结果） p> Ooops. And that is why a sorting algorithm can fail (in the spec, this is be "implementation-dependent behaviour" - i.e. unpredictable results) when it is invoked with a comparison function that is not consistent.由于在许多其他语言中，有排序算法，不希望三向比较，而只是一个布尔小于操作符。 C ++ std :: sort 是一个很好的例子的。如果需要确定等式，它将简单地应用两次交换的参数。当然，这可以更有效率并且不易出错，但如果操作者无法内联，则需要更多的调用到比较函数。Because in many other languages, there are sorting algorithms that don't expect a three-way comparison but merely a boolean smaller-than operator. C++ std::sort is a good example of that. It will simply be applied twice with swapped arguments if an equality needs to be determined. Admittedly, this can be more efficient and is less error-prone, but needs more calls to the comparison function if the operator cannot be inlined.只有通过运气，如果你尝试了一些随机的例子。 Only by sheer luck, if you tried some random example. Or because your test suite is flawed - incorrect and/or incomplete.这是我用来找到上述最小反例的小脚本：Here is the small script I used to find the above minimal counterexample:function perms(n, i, arr, cb) {// calls callback with all possible arrays of length n if (i >= n) return cb(arr); for (var j=0; j<n; j++) { arr[i] = j; perms(n, i+1, arr, cb); }}for (var i=2; ; i++) // infinite loop perms(i, 0, [], function(a) { if ( a.slice().sort(function(a,b){ return a>b }).toString() != a.slice().sort(function(a,b){ return a-b }).toString() ) // you can also console.log() all of them, but remove the loop! throw a.toString(); }); 什么比较函数是正确的？ 当你想要一个词典排序时，根本不使用比较函数。 What comparison function is correct?Use no comparison function at all, when you want a lexicographic sort. Items in the array will be stringified if necessary.像关系运算符一样工作的通用比较函数可以实现为A generic comparison function that works like the relational operators can be implemented asfunction(a, b) { if (a > b) return 1; if (a < b) return -1; /* else */ return 0;} 使用一些技巧，这可以缩小为等效 function（a，b）{return +（a> b）|| - （a 。 对于数字，您可以简单地返回它们的差值，它们遵守上述所有法则：For numbers, you can simply return their difference, which abides all the laws above:function(a, b) { return a - b; // but make sure only numbers are passed (to avoid NaN)}要反向排序，只需取适当的一个，并用 b 交换 a 。If you want to sort in reverse, just take the appropriate one and swap a with b.如果要对复合类型（对象等）进行排序，请替换每个 a 和每个 b 访问所讨论的属性，或者方法调用或任何你想要排序的。If you want to sort composite types (objects etc), replace each a and each b with an access of the properties in question, or a method call or whatever you want to sort by. 这篇关于JavaScript中的排序：不应该返回一个布尔值足以用于比较函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！