它们使用相同的数组:
快速排序时间: 3159毫秒(数组长度10K)
气泡排序时间: 1373毫秒(数组长度10K)
我试着用快速和气泡排序算法来比较排序的时间。我使用10K不同随机数的数组对这两个函数进行随机排序。但由于某些原因,冒泡排序总是比快速排序快,即使气泡排序的平均时间复杂度比快速排序的平均时间复杂度更差。为什么在我的例子中,气泡排序算法比快速排序算法慢?(我尝试了不同的数组长度,从10到10K)
那是我的快速排序功能
let quickSort = (arr) => {
if (arr.length <= 1) {
return arr
}
const pivot = arr[0]
const rest = arr.slice(1);
let left = [],
right = [];
rest.forEach(el => el > pivot ? right = [...right, el] : left = [...left, el]);
return [...quickSort(left), pivot, ...quickSort(right)];
}这就是我的泡泡排序函数
let bubbleSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let s = i + 1; s < arr.length; s++) {
if (arr[s] < arr[i]) {
let a = arr[i];
arr[i] = arr[s]
arr[s] = a;
}
}
}
return arr
}发布于 2021-12-11 01:09:35
就像巴玛尔说的,快速排序正在复制大量的东西。
另外,每个扩展算子(3点操作符)的复杂度为O(n),因为它遍历整个数组(就像一个简单的for循环),这也可能使算法变得更慢。
https://stackoverflow.com/questions/70311856
复制相似问题