我已经实现了归并排序和快速排序，并将它们与本机JavaScript排序进行了比较。对于快速排序，我尝试使用此算法：在youtube上查看算法。两种算法都尽可能地使用较少的内存，对于归并排序，为每个递归调用传递一个辅助数组（以避免开销），对于快速排序，则传递起始和结束位置的位置。 我正在使用这些排序来管理NodeJs应用程序中的大量数据。
以下是归并排序，快速排序和本机JavaScript排序，您可以测试其性能
问题是：为什么本机JavaScript执行得更慢？
在我的情况下：
Chrome - 归并排序：测量：1997.920毫秒； 快速排序：测量：1755.740毫秒； 本机：测量：4988.105毫秒
节点：归并排序：测量：2233.413毫秒； 快速排序：测量：1876.055毫秒； 本机：测量：6317.118毫秒
Merge Sort
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]);Quicksort
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');Native Javascript Sort
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]);
<,>,或==重写mergeSort和quickSort，我会很感兴趣看看它们的时间表现如何。 - Hamms