javascript - 在 JavaScript 中对大型(ish)数字数组进行排序的最快方法是什么

Question

在我的应用程序中，我需要对随机数的大型数组(100,000 到 1,000,000 之间)进行排序。

我一直在使用内置的 array.sort(comparisonFunction)，其中 comparisonFunction 如下所示:

function comparisonFunction(a,b) {
    return a-b;
}

这工作得很好，但我读过(例如，Native JavaScript sort performing slower than implemented mergesort and quicksort)有更快的选择，特别是如果您的要求满足特定条件:

1. 我只需要对数字进行排序(例如，不是对象或字母数字数据)
2. 数据是随机的(不可能是已经排序的)
3. 排序不需要稳定

那么 - 在这些情况下可用的最快(或足够接近)排序算法是什么？

还有，是否有规范的(或至少是相对理想的)JavaScript 实现？

[更新]

所以，快速澄清 - 在链接的问题中，OP 需要稳定的排序。因为我不知道 - 我想知道这是否会改变答案(即，如果您事先知道您的数据不会被预先排序，并且您不需要稳定的排序)。

也许答案是“否”，但这就是我要问的原因。

[更新#2]

这是一个快速排序的实现，除非我犯了错误 - 轻松击败原生排序功能:

function comparisonFunction(a, b) {
  return a - b;
}

function quickSort(arr, leftPos, rightPos, arrLength) {
  let initialLeftPos = leftPos;
  let initialRightPos = rightPos;
  let direction = true;
  let pivot = rightPos;
  while ((leftPos - rightPos) < 0) {
    if (direction) {
      if (arr[pivot] < arr[leftPos]) {
        quickSort.swap(arr, pivot, leftPos);
        pivot = leftPos;
        rightPos--;
        direction = !direction;
      } else
        leftPos++;
    } else {
      if (arr[pivot] <= arr[rightPos]) {
        rightPos--;
      } else {
        quickSort.swap(arr, pivot, rightPos);
        leftPos++;
        pivot = rightPos;
        direction = !direction;
      }
    }
  }
  if (pivot - 1 > initialLeftPos) {
    quickSort(arr, initialLeftPos, pivot - 1, arrLength);
  }
  if (pivot + 1 < initialRightPos) {
    quickSort(arr, pivot + 1, initialRightPos, arrLength);
  }
}
quickSort.swap = (arr, el1, el2) => {
  let swapedElem = arr[el1];
  arr[el1] = arr[el2];
  arr[el2] = swapedElem;
}

var
  i,
  arr1, arr2,
  length;

length = 1000000;


arr1 = [];
arr2 = [];
for (i = 0; i < length; i++) {
  arr1.push(Math.random());
  arr2.push(Math.random());
}

console.time("nativeSort");
arr1.sort(comparisonFunction);
console.timeEnd("nativeSort");


console.time("quickSort");
quickSort(arr2, 0, length - 1, length);
console.timeEnd("quickSort");

Answer 1

有一些排序实现始终击败股票 .sort(至少 V8)，node-timsort成为其中一员。示例:

var SIZE = 1 << 20;

var a = [], b = [];

for(var i = 0; i < SIZE; i++) {
    var r = (Math.random() * 10000) >>> 0;
    a.push(r);
    b.push(r);
}

console.log(navigator.userAgent);

console.time("timsort");
timsort.sort(a, (x, y) => x - y);
console.timeEnd("timsort");

console.time("Array#sort");
b.sort((x, y) => x - y);
console.timeEnd("Array#sort");

<script src="https://rawgithub.com/mziccard/node-timsort/master/build/timsort.js"></script>

以下是我使用的不同浏览器的一些计时(有人使用 Chakra 吗？):

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/53.0.2785.113 Safari/537.36
timsort: 256.120ms
Array#sort: 341.595ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/602.2.14 (KHTML, like Gecko) Version/10.0.1 Safari/602.2.14
timsort: 189.795ms
Array#sort: 245.725ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:51.0) Gecko/20100101 Firefox/51.0
timsort: 402.230ms
Array#sort: 187.900ms

因此，FF 引擎与 Chrome/Safari 有很大不同。