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

Question

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

我一直在使用内置的array.sort(comparisonFunction)compareFunction看起来像这样:

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

这很好用,但我读过(例如,Native JavaScript排序执行比实现的mergesort和quicksort慢),有更快的选项,特别是如果您的要求满足特定条件:

1. 我只需要对数字进行排序(例如,不是对象或字母数字数据)
2. 数据是随机的(没有机会已经订购)
3. 排序不需要稳定

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

并且,是否存在规范(或至少相对理想)的JavaScript实现？

[UPDATE]

Yikes ...发布后30秒内两张投票!因此,快速澄清 - 在相关问题中,OP需要稳定的排序.因为我没有 - 我想知道这是否会改变答案(也就是说,如果您事先知道您的数据不会被预先排序,并且您不需要稳定的排序,也许可以使用更快的排序选项).

也许答案是"不",但这就是我要问的原因.

[更新#2]

这是quicksort的一个实现,除非我犯了一个错误 - 轻松地击败本机排序函数:

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非常不同.

Answer 2

对数字数组进行排序的最快方法是将其转换为TypedArraythen 调用其sort函数。Array.sort()类型化数组上的排序函数默认为数字，并且比比较函数快得多。

const a = Array.from({length: 1<<20}, Math.random)
const b = Array.from(a)

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

console.time("nativeSort")
a.sort(comparisonFunction)
console.timeEnd("nativeSort")

console.time("typedSort")
let typedArray = Float32Array.from(b)
typedArray.sort()
console.timeEnd("typedSort")

Answer 3

无需将其标记为答案，因为它不是 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 排序执行速度比实现的合并排序和快速排序慢

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