在 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");

原文由 mattstuehler 发布，翻译遵循 CC BY-SA 4.0 许可协议

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>

以下是我使用的不同浏览器的一些时间（脉轮有人吗？）：

 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 有很大不同。

原文由 georg 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

无需将此标记为答案，因为它不是 javascript，并且没有 introsort 的深度检查以切换到堆排序。

示例 C++ 快速排序。它使用 3 的中位数来选择枢轴值，Hoare 分区方案，然后排除中间值 == 枢轴（这可能会或可能不会改善时间，因为值 == 枢轴可以在分区步骤中的任何地方结束），并且仅在较小的分区，在较大的分区上循环以将堆栈复杂度限制为 O(log2(n)) 最坏情况。最坏情况下的时间复杂度仍然是 O(n^2)，但这需要中位数为 3 才能重复选择较小或较大的值，这是一种不寻常的模式。已排序或反向排序的数组不是问题。如果所有值都相同，则时间复杂度为 O(n)。添加深度检查以切换到堆排序（使其成为内插排序）会将时间复杂度限制为 O(n log(n))，但具有更高的常数因子，具体取决于使用了多少堆排序路径。

 void QuickSort(uint32_t a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        uint32_t p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        while(i > lo && a[i] == p)  // exclude middle values == pivot
            i--;
        while(k < hi && a[k] == p)
            k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}

如果空间不是问题，那么这里的合并排序可能会更好：

本机 JavaScript 排序执行速度比实现的合并排序和快速排序慢

如果只是对数字进行排序，并再次假设空间不是问题，基数排序将是最快的。

原文由 rcgldr 发布，翻译遵循 CC BY-SA 4.0 许可协议