javascript - Array.sort在iOS中获得不同的结果

这是一个简单的代码，但是在Andriod和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

最佳答案

javascript引擎对其排序功能使用不同的算法。由于compare函数不会比较值，因此您将获得不同算法的内部工作结果，而不是获得排序结果。

查看 V8 引擎(Chrome)和 JavaScriptCore 的源代码(似乎由Safari使用，或者至少sort函数给出相同的结果，所以我猜它使用相同的算法)，可以查看正在使用的功能。

并不是说它可能不完全是所使用的函数，重要的是算法是不同的。如果您实际比较值，它们会给出相同的结果，但是如果不比较，则结果取决于它们的运算方式，而不是函数本身。至少不是完全。

这是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;
}))

同样，这些可能并不完全是每个浏览器中使用的功能，但是它向您展示了如果您不实际比较值，不同的算法将如何表现。