1
私のアプリケーションでは、大きな配列（100,000〜1,000,000）の乱数をソートする必要があります。JavaScriptで大きな（ish）配列をソートする最も速い方法は何ですか
私はcomparisonFunctionは次のようになりarray.sort(comparisonFunction)に建て使用してきた
：特にあなたの場合は、より高速な選択肢があること
function comparisonFunction(a,b) {
return a-b;
}
これはうまく動作しますが、私が読んだ（例えば、Native JavaScript sort performing slower than implemented mergesort and quicksortを）要件は、特定の条件を満たし：
- 私は数字だけ（例えば、オブジェクトではなく、または英数字データ）をソートする必要が
- データであるランダム（それはすでに注文したということはチャンスがない）
- ソートが
が安定している必要はありません - 最速のものです（または近いです十分な）ソートアルゴリズムは、これらの状況で利用可能ですか？
そして、正規の（または少なくとも比較的理想的な）JavaScript実装がありますか？
[UPDATE]
む〜... 2投稿の30秒以内に投票ダウン！したがって、簡単な説明 - リンクされた質問では、OPは安定した並べ替えが必要でした。あなたがデータをあらかじめソートされていないことがわかっていれば、答えが変わるかどうかは分かりません（つまり、おそらくもっと速いソートオプションがあるかもしれません）。安定した分類）。
おそらく答えは「いいえ」ですが、それが私が求めている理由です。
[UPDATE＃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");
*」...私は、はるかに高速の選択肢があることを読みました... "*どこ？ –
ネイティブJavaScriptの '.sort（）'は安定している必要はありません。私はJavaScriptのソートがどんな有意なサイズの配列のネイティブなソートよりも速かったならば、私は驚くだろうが、特定の入力制約では、基数ソートは試してみる価値があるかもしれない。 – Pointy
@Liam：上記は明らかに、安定した並べ替えを必要としないことを示しています。 （あなたが数字を並べ替えるのであれば、安定しているか不安定であるか区別することはできません...） –