首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >为什么在我的情况下,快速排序总是比泡沫排序慢?

为什么在我的情况下,快速排序总是比泡沫排序慢?
EN

Stack Overflow用户
提问于 2021-12-11 00:54:03
回答 1查看 162关注 0票数 0

它们使用相同的数组:

快速排序时间: 3159毫秒(数组长度10K)

气泡排序时间: 1373毫秒(数组长度10K)

我试着用快速和气泡排序算法来比较排序的时间。我使用10K不同随机数的数组对这两个函数进行随机排序。但由于某些原因,冒泡排序总是比快速排序快,即使气泡排序的平均时间复杂度比快速排序的平均时间复杂度更差。为什么在我的例子中,气泡排序算法比快速排序算法慢?(我尝试了不同的数组长度,从10到10K)

那是我的快速排序功能

代码语言:javascript
运行
复制
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)];
}

这就是我的泡泡排序函数

代码语言:javascript
运行
复制
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
}
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2021-12-11 01:09:35

就像巴玛尔说的,快速排序正在复制大量的东西。

另外,每个扩展算子(3点操作符)的复杂度为O(n),因为它遍历整个数组(就像一个简单的for循环),这也可能使算法变得更慢。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/70311856

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档