12
我已經實現了一個mergesort和一個快速排序來比較它們與本機JavaScript排序。對於快速排序，我嘗試使用此算法：view algorithm on youtube。兩種算法都使用盡可能少的內存，對於合併排序，每次遞歸調用都會傳遞一個輔助數組（以避免開銷），對於快速排序來說，起始和結束位置的位置也是如此。我正在使用排序來管理NodeJs應用程序中的大量數據。本機JavaScript排序執行比實施mergesort和quicksort慢
下面你有歸併，快速排序和本地JavaScript的排序和您可以測試性能
的問題是：爲什麼本地JavaScript執行速度較慢？
在我的情況下：
Chrome - 合併排序：措施：1997.920ms;快速排序：測量：1755.740ms; native：測量：4988.105ms
節點：合併排序：測量：2233.413ms;快速排序：測量：1876.055ms;本地：措施：6317.118ms
歸併排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
function merge(arr, aux, lo, mid, hi) {
for (var k = lo; k <= hi; k++) {
aux[k] = arr[k];
}
var i = lo;
var j = mid + 1;
for (var k = lo; k <= hi; k++) {
if (i > mid) {
arr[k] = aux[j++];
} else if (j > hi) {
arr[k] = aux[i++];
} else if (aux[i] < aux[j]) {
arr[k] = aux[i++];
} else {
arr[k] = aux[j++];
}
}
}
function sort(array, aux, lo, hi) {
if (hi <= lo) return;
var mid = Math.floor(lo + (hi - lo)/2);
sort(array, aux, lo, mid);
sort(array, aux, mid + 1, hi);
merge(array, aux, lo, mid, hi);
}
function merge_sort(array) {
var aux = array.slice(0);
sort(array, aux, 0, array.length - 1);
return array;
}
return merge_sort(array);
}
console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0], arr[1]);快速排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
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;
}
arrLength = arr.length;
console.time('measure');
quickSort(arr, 0, arrLength - 1, arrLength);
console.log(arr[0], arr[1]);
console.timeEnd('measure');本地JavaScript排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 100000000));
}
console.time('measure');
arr.sort(function compareNumbers(a, b) {
return a - b;
});
console.timeEnd('measure');
console.log(arr[0], arr[1]);
僅供參考，第一個是最慢的第二個最快的考慮我的電腦和隨機性:) – Lucio
是，快速排序執行最快..所以原生js執行比你的電腦合併排序更好？ –
有趣。我在Firefox和Edge中檢查了這些。雖然本地排序仍然是最慢的，但他們三人在Firefox中的差異並不那麼大。在Edge中，第一個沒有完成，或者我放棄得太快。它似乎永遠不會完成。最後兩個在Edge中完成。 – jfriend00