javascript - Array.sort 在 IOS 中得到不同的结果

Question

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

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

同样，这些可能不完全是每个浏览器中使用的函数，但它向您展示了如果您不实际比较值，不同算法的行为方式。