Array.sort在IOS中得到不同的结果 [英] Array.sort get different result in IOS

问题描述

这是一个简单的代码，但在Andriod和Iphone中返回不同的结果。

it's a simple code, but returns different results in Andriod and 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的索引。
  compareFunction（a，b）在给定一对特定元素a和b作为其两个参数时必须始终返回相同的值。如果返回不一致的结果，则排序顺序未定义。

因此结果应为1,2,3,4,5。
但它是Iphone它显示5,4,3,2,1

So the result should be 1,2,3,4,5. But is Iphone it shows 5,4,3,2,1

这是一个链接供您试用此代码。 http://www.madcoder.cn/demos/ios-test.html

Here is a link for you to try this code. http://www.madcoder.cn/demos/ios-test.html

在我做了越来越多的测试之后。我发现Iphone正在进行不同的排序。
这是一个显示排序如何工作的链接： http：//www.madcoder。 cn / demos / ios-test2.html

And after I did more and more test. I found Iphone is doing a different sorting. Here is a link shows how sort works: http://www.madcoder.cn/demos/ios-test2.html

推荐答案

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

The javascript engines use different algorithms for their sort function. Since the compare function doesn't compare values, you get the result of the inner workings of the different algorithms instead of having a sorted result.

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

Looking at the source code of V8 engine (Chrome) and JavaScriptCore (which seems to be used by Safari, or at least the sort function gives the same result, so I guess it uses the same kind of algorithm), you can view the functions that are being used.

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

Not that it might not be exactly the functions used, what's important is that the algorithms are different. They give the same result if you actually compare values, but if not, the result is dependent on the way they operate, not on the function itself. At least not completely.

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

Here's V8 engine sorting function. You'll see that for arrays bigger than 10 elements, the algorithm isn't the same, so the result for arrays smaller than 10 elements is different than for those bigger than 10 elements.

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

You can find following algorithms here: 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

And JavaScriptCore uses merge sort. You can find this algorithm here: 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;
}))

同样，这些可能并不完全是每个浏览器中使用的函数，但它会告诉您如果不这样做，不同的算法将如何表现实际比较值。

Again these may not be exactly the functions used in each browser, but it shows you how different algorithms will behave if you don't actually compare values.

这篇关于Array.sort在IOS中得到不同的结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！