在iOS中，Array.sort得到不同的结果

Question

这是一个简单的代码，在安卓和iPhone上返回不同的结果。

var str = [1,2,3,4,5].sort(function () {
    return -1;
})
document.write(str);

在MDN(https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort)中提到：

• 如果compareFunction(a, b)小于0，则将a排序到比b更低的索引，即a排在前面。
• 如果compareFunction(a, b)返回0，则保持a和b相对位置不变，但与所有其他元素相比进行排序。注意：ECMAscript标准不保证此行为，因此并非所有浏览器（例如至少2003年之前的Mozilla版本）都支持此行为。
• 如果compareFunction(a, b)大于0，则将b排序到比a更低的索引。 当给定特定的一对元素a和b作为其两个参数时，compareFunction(a, b)必须始终返回相同的值。如果返回不一致的结果，则排序顺序是未定义的。

因此，结果应该是1、2、3、4、5。 但在iPhone上，它显示为5、4、3、2、1。

这里有一个链接供您尝试此代码。http://www.madcoder.cn/demos/ios-test.html 我做了越来越多的测试后发现，iPhone正在进行不同的排序。 这里有一个链接显示了排序的工作原理：http://www.madcoder.cn/demos/ios-test2.html

- Gcaufy

---

你的排序函数无效。它对于所有的参数对都返回“-1”，而不考虑它们的顺序。这意味着像 [1,2] 和 [2,1] 这样的对都会返回 -1。 这意味着你的排序函数实际上根本没有对数组进行排序。输出结果被排序是偶然发生的。详情请参见 https://jsfiddle.net/rq7bnsxd/。 - Dancrumb

@Tushar，我知道你的代码是有效的，但我只是想知道为什么。 - Gcaufy

就像 @Dancrumb 说的那样， 我投票赞成重新打开，但回想起来，可能不应该这样做。 如果每个值都返回相同的结果，那么你基本上是在说“没有顺序；按照排序算法进行操作即可。” 虽然你也许可以使用它来弄清楚使用了哪个算法。 - Dave Newton

@Dancrumb 没错，-1不能进行排序。但在iPhone上，它可以进行排序。这就是问题所在。 - Gcaufy

@Gcaufy 这个数组 看起来 是有序的，因为当没有自然顺序时，它的排序算法会得出这样的结果。但实际上它并不是“有序”的，而是反向排列的。例如，你可以尝试 [1, 3, 2, 4, 6, 5, 8, 7]。 - Dave Newton

Answer 1

JavaScript引擎使用不同算法进行排序函数。由于比较函数不比较值，所以您得到的是不同算法内部运作的结果，而不是排序后的结果。

查看V8 引擎（Chrome）和JavaScriptCore（似乎被Safari使用，或者至少排序函数给出了相同的结果，因此我猜它使用了相同类型的算法）的源代码，您可以查看正在使用的函数。

注意，它可能不是实际使用的函数，重要的是算法是不同的。如果您实际比较值，则它们会给出相同的结果，但如果没有，结果取决于它们的操作方式，而不仅仅是函数本身。至少不是完全一样的。

这里是V8引擎排序函数。您将看到对于大于10个元素的数组，算法不同，因此小于10个元素的数组的结果与大于10个元素的数组的结果不同。

您可以在此处找到以下算法: https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/js/array.js&q=array&sq=package:chromium&dr=C

comparefn = function(a, b) {
  return -1
}
var InsertionSort = function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i];
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j];
      var order = comparefn(tmp, element);
      if (order > 0) {
        a[j + 1] = tmp;
      } else {
        break;
      }
    }
    a[j + 1] = element;
  }

  console.log(a);
}
var GetThirdIndex = function(a, from, to) {
  var t_array = new InternalArray();
  // Use both 'from' and 'to' to determine the pivot candidates.
  var increment = 200 + ((to - from) & 15);
  var j = 0;
  from += 1;
  to -= 1;
  for (var i = from; i < to; i += increment) {
    t_array[j] = [i, a[i]];
    j++;
  }
  t_array.sort(function(a, b) {
    return comparefn(a[1], b[1]);
  });
  var third_index = t_array[t_array.length >> 1][0];
  return third_index;
}


var QuickSort = function QuickSort(a, from, to) {

  var third_index = 0;
  while (true) {
    // Insertion sort is faster for short arrays.
    if (to - from <= 10) {
      InsertionSort(a, from, to);
      return;
    }
    if (to - from > 1000) {
      third_index = GetThirdIndex(a, from, to);
    } else {
      third_index = from + ((to - from) >> 1);
    }

    // Find a pivot as the median of first, last and middle element.
    var v0 = a[from];
    var v1 = a[to - 1];
    var v2 = a[third_index];
    var c01 = comparefn(v0, v1);
    if (c01 > 0) {
      // v1 < v0, so swap them.
      var tmp = v0;
      v0 = v1;
      v1 = tmp;
    } // v0 <= v1.
    var c02 = comparefn(v0, v2);
    if (c02 >= 0) {
      // v2 <= v0 <= v1.
      var tmp = v0;
      v0 = v2;
      v2 = v1;
      v1 = tmp;
    } else {
      // v0 <= v1 && v0 < v2
      var c12 = comparefn(v1, v2);
      if (c12 > 0) {
        // v0 <= v2 < v1
        var tmp = v1;
        v1 = v2;
        v2 = tmp;
      }
    }
    // v0 <= v1 <= v2
    a[from] = v0;
    a[to - 1] = v2;
    var pivot = v1;
    var low_end = from + 1; // Upper bound of elements lower than pivot.
    var high_start = to - 1; // Lower bound of elements greater than pivot.
    a[third_index] = a[low_end];
    a[low_end] = pivot;

    // From low_end to i are elements equal to pivot.
    // From i to high_start are elements that haven't been compared yet.
    partition: for (var i = low_end + 1; i < high_start; i++) {
      var element = a[i];
      var order = comparefn(element, pivot);
      if (order < 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
      } else if (order > 0) {
        do {
          high_start--;
          if (high_start == i) break partition;
          var top_elem = a[high_start];
          order = comparefn(top_elem, pivot);
        } while (order > 0);
        a[i] = a[high_start];
        a[high_start] = element;
        if (order < 0) {
          element = a[i];
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        }
      }
    }
    if (to - high_start < low_end - from) {
      QuickSort(a, high_start, to);
      to = low_end;
    } else {
      QuickSort(a, from, low_end);
      from = high_start;
    }
  }


};



InsertionSort([1, 2, 3, 4, 5], 0, 5);

//QuickSort is recursive and calls Insertion sort, so you'll have multiple logs for this one
QuickSort([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], 0, 13);

//You'll see that for arrays bigger than 10, QuickSort is called.
var srt = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].sort(function() {
  return -1
})

console.log(srt)

JavaScriptCore使用归并排序算法。你可以在这里找到该算法的实现代码： http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/builtins/ArrayPrototype.js

function min(a, b) {
  return a < b ? a : b;
}

function merge(dst, src, srcIndex, srcEnd, width, comparator) {
  var left = srcIndex;
  var leftEnd = min(left + width, srcEnd);
  var right = leftEnd;
  var rightEnd = min(right + width, srcEnd);

  for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
    if (right < rightEnd) {
      if (left >= leftEnd || comparator(src[right], src[left]) < 0) {
        dst[dstIndex] = src[right++];
        continue;
      }
    }

    dst[dstIndex] = src[left++];
  }
}

function mergeSort(array, valueCount, comparator) {
  var buffer = [];
  buffer.length = valueCount;

  var dst = buffer;
  var src = array;
  for (var width = 1; width < valueCount; width *= 2) {
    for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
      merge(dst, src, srcIndex, valueCount, width, comparator);

    var tmp = src;
    src = dst;
    dst = tmp;
  }

  if (src != array) {
    for (var i = 0; i < valueCount; i++)
      array[i] = src[i];
  }

  return array;
}


console.log(mergeSort([1, 2, 3, 4, 5], 5, function() {
  return -1;
}))

这些可能不是每个浏览器实际使用的函数，但它们展示了如果您不真正比较值，不同算法将如何表现。

- Julien Grégoire

---

首先我在 Webkit 代码中测试了算法。它的表现不像 iPhone 那样，但无论如何，我已经有了想法。 - Gcaufy

这是否意味着 Webkit 实现该方法的方式不符合标准？因为文档中说：“如果 compareFunction(a, b) 小于 0，则将 a 排序到比 b 更低的索引，即 a 先出现。” - Gcaufy

但是你不知道a和b会是什么。这就是算法生成它们并确定它们的评估顺序的作用。例如，如果'a'在数组中在'b'后面，并且具有比'b'更高的值。然后，比较函数'a-b'将返回正数，这意味着不需要排序。但是，如果您推入负数，则强制进行不应该完成的排序。标准没有说明compareFunction的'a'和'b'将按索引顺序传递。这就是为什么返回固定值会给出取决于算法的顺序的原因。 - Julien Grégoire