javascript - 合并快速排序时间结果异常
问题描述
我目前正在为我的扩展论文进行调查。我正在测试合并和快速排序算法之间的比较。我的结果出现了这种奇怪的异常。我的第二个 for 循环中的每个第一个排序返回的时间都比其他排序要长得多。我不知道为什么,有人可以解释一下吗?
出于某种原因,JSFiddle 不会输出任何内容,尽管当我在本地运行它时它工作正常。所以,我将在这里发布代码:
function generateRandomArray(l, min, max) {
var a = [];
for (var i = 0; i < l; i++) {
a.push(Math.ceil(Math.random() * max + min - 1));
}
return a;
}
function quickSort(a) {
var less = [],
pivotList = [],
greater = [];
if (a.length <= 1) return a;
var pivot = a[0];
for (var i = 0; i < a.length; i++) {
if (a[i] < pivot) less.push(a[i]);
else if (a[i] > pivot) greater.push(a[i]);
else pivotList.push(a[i]);
}
less = quickSort(less);
greater = quickSort(greater);
return less.concat(pivotList, greater);
}
function mergeSort(left, right) {
if (!left) return right;
if (!right) return left;
var result = [],
leftIndex = 0,
rightIndex = 0;
while (leftIndex < left.length & rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
if (leftIndex != left.length) {
var temp = left.slice(leftIndex, left.length);
result = result.concat(temp);
} else if (rightIndex != right.length) {
var temp = right.slice(rightIndex, right.length);
result = result.concat(temp);
}
return result;
}
function mergeSortSplit(a) {
if (a.length <= 1) return a;
var middle = Math.floor(a.length / 2);
var left = a.slice(0, middle),
right = a.slice(middle, a.length);
left = mergeSortSplit(left);
right = mergeSortSplit(right);
return mergeSort(left, right);
}
window.onload = function() {
var timeResults = [
[[], [], [], [], []],
[[], [], [], [], []]
];
for (var i = 0; i < 10; i++) {
for (var j = 3; j < 6; j++) {
var array = generateRandomArray(Math.pow(10, j), 1, 100);
var mergeSortTime = window.performance.now();
mergeSortSplit(array);
timeResults[0][j - 3].push(window.performance.now() - mergeSortTime);
var quickSortTime = window.performance.now();
quickSort(array);
timeResults[1][j - 3].push(window.performance.now() - quickSortTime);
}
}
for (var i = 0; i < timeResults.length; i++) {
document.getElementById("demo").innerHTML += "<b>" + (i + 1) + ". </b><br>";
for (var j = 0; j < timeResults[i].length; j++) {
document.getElementById("demo").innerHTML += "<b>" + Math.pow(10, j + 3) + ": </b>";
for (k = 0; k < timeResults[i][j].length; k++) {
document.getElementById("demo").innerHTML += timeResults[i][j][k] + "<b> | </b>";
}
document.getElementById("demo").innerHTML += "<br><br>";
}
document.getElementById("demo").innerHTML += "<br><br><br>";
}
console.log(timeResults);
}
<html>
<head>
<meta charset="utf-8">
<title>EE Investigation</title>
<script type="text/javascript" src="index.js"></script>
</head>
<body>
<p id="demo"></p>
</body>
</html>
解决方案
推荐阅读
- c++ - 为什么 fwrite 向我抛出访问冲突?
- sql-server - MS Visual Studio 现有保存的 sql 文件无法从服务器资源管理器访问保存的数据库连接
- python-3.x - while循环和使用after重复调用函数的区别
- sql - Power BI NativeQuery - 无法从类型转换为文本
- scala - 迁移到 scala-js 1.1.1 时出现 scala-js“@JSGlobalScope”错误
- ruby-on-rails - STRIPE :此客户没有附加付款来源或默认付款方式。轨道上的红宝石
- codenameone - 需要你点亮 iOS 线程
- python - 使用逻辑回归的文本数据
- python - 用 NaN 替换数据框值
- laravel - 将失败的队列作业记录到文件回退