我在nodejs里运行比快速排序慢了一倍 #1
Description
const quickSort = (array) => {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {
return
}
let i = left
let j = right
const baseVal = arr[j]
while (i < j) {
while (i < j && arr[i] <= baseVal) {
i++
}
arr[j] = arr[i]
while (j > i && arr[j] >= baseVal) {
j--
}
arr[i] = arr[j]
}
arr[j] = baseVal /
sort(arr, left, j - 1)
sort(arr, j + 1, right)
}
const newArr = array.concat()
sort(newArr)
return newArr
}
function chenSort(list) {
if (list.length < 2) {
return;
}
let maxValue = list[0];
let minValue = maxValue;
for (let i = 1, len = list.length; i < len; ++i) {
if (list[i] > maxValue) {
maxValue = list[i];
}
if (list[i] < minValue) {
minValue = list[i];
}
}
if (maxValue === minValue) {
return;
}
let bucketSize = Math.min(list.length, 5000);
let maxBucketIndex = bucketSize - 1;
let buckets = new Array(bucketSize);
let slot;
const factor = maxBucketIndex / (maxValue - minValue);
for (let i = 0, len = list.length; i < len; ++i) {
slot = Math.trunc((list[i] - minValue) * factor);
if (buckets[slot] === undefined) {
buckets[slot] = [];
}
buckets[slot].push(list[i]);
}
function compare(left, right) {
return left - right;
}
let index = 0;
for (let i = 0, len = buckets.length; i < len; ++i) {
if (buckets[i] != null) {
if (buckets[i].length > 1) {
if (buckets[i].length >= 1000) {
chenSort(buckets[i]);
} else {
buckets[i].sort(compare);
}
for (let element of buckets[i]) {
list[index++] = element;
}
} else {
list[index++] = buckets[i][0];
}
}
}
}
function main() {
let arr = [];
for (let i = 0; i < 100000000; ++i) {
arr.push(Math.ceil(Math.random() * 1000000));
}
let startTime = new Date();
quickSort(arr);
console.log(`快速排序完成，用时: ${new Date()-startTime}`);
startTime = new Date();
chenSort(arr);
console.log(`chen排序完成，用时: ${new Date()-startTime}`);
}
main();