javascript - 为什么这种排序算法会在浏览器中产生不一致的结果？

Question

我正在尝试用 Javascript 实现一个(确实非常简单的)绝对偏差排序算法。绝对偏差定义为一种元素与所有元素的平均值之差的绝对值。例如，给定元素1、4、5、9，平均值为(1 + 4 + 5 + 9)/4 = 4.75，则每个元素的绝对偏差计算如下:

• absDev(1) = |1 - 4.75| = 3.75
• absDev(4) = |4 - 4.75| = 0.75
• absDev(5) = |5 - 4.75| = 0.25
• absDev(9) = |9 - 4.75| = 4.25

因此，通过升序绝对偏差对元素进行排序将得到序列 5、4、1、9。到目前为止一切顺利，我当前的 Javascript 实现在不同的浏览器中给出了不同的结果。

这是:http://jsfiddle.net/WVvuu/

• 在 Firefox 和 Safari 中，我得到了预期的结果 5、4、1、9
• 在 Chrome 和 Opera 中，我得到 4、5、1、9
• 在 IE 10 中，我得到 1、4、5、9

我想我的代码中一定有一些非常简单的错误，但我似乎找不到它。我想了解它有什么问题，以及为什么我在更换浏览器时会得到不同的结果。如果有人能友好地解释我所缺少的东西，我将不胜感激。同样，这是代码:

var array = [1, 4, 5, 9];

function absDev(x) {
    return Math.abs(x - average(array));
}

function average(array) {
    var sum = array.reduce(function(previousValue, currentValue) {
        return previousValue + currentValue;
    }, 0);
    return sum / array.length;
}

array.sort(function(x, y) {
    return absDev(x) - absDev(y);
});

alert("Sorted array: " + array);

Answer 1

我怀疑这是因为在进行排序时数组的状态不一定是一致的。无论如何，您真的不应该重新计算每次比较的平均值:

array.sort(function(array) {
  var avg = array.reduce(function(previousValue, currentValue) {
    return previousValue + currentValue;
  }, 0);
  avg /= array.length;
  return function(x, y) {
    return Math.abs(x - avg) - Math.abs(y - avg);
  };
}(array));

看看效果是否更好。 (编辑 — 它在 Chrome 中为我提供了正确答案。)

更详细地说，我怀疑您看到奇怪结果的排序函数可能会在适当的位置对数组执行交换，并且可能会有一个或多个原始数组值丢失或复制的时间间隔排序机制正在发挥作用。因此，您的平均函数看到一个数组(有时)具有不同的值列表，这意味着平均值(有时)不同。