热门标签 | HotTags
当前位置:  开发笔记 > 前端 > 正文

冒泡排序、快速排序和堆排序的时间复杂度是多少

冒泡排序的时间复杂度:最好情况是“O(n)”,最坏情况是“O(n2)”。快速排序的的时间复杂度:最好情况是“O(nlogn)”,最坏情况是“O(n2)”。堆排序的时间复杂度是“O(nlogn)”。

冒泡排序的时间复杂度:最好情况是“O(n)”,最坏情况是“O(n2)”。快速排序的的时间复杂度:最好情况是“O(nlogn)”,最坏情况是“O(n2)”。堆排序的时间复杂度是“O(nlogn)”。

稳定,因为if判断不成立,就不会交换顺序,不会交换相同元素

  • 冒泡排序它在所有排序算法中最简单。然而, 从运行时间的角度来看,冒泡排序是最差的一个,它的复杂度是O(n2)

  • 冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。

  • 交换时,我们用一个中间值来存储某一交换项的值。其他排序法也会用到这个方法,因此我 们声明一个方法放置这段交换代码以便重用。使用ES6(ECMAScript 2015)**增强的对象属性——对象数组的解构赋值语法,**这个函数可以写成下面 这样:

[array[index1], array[index2]] = [array[index2], array[index1]];

具体实现:

function bubbleSort(arr) {
  for (let i = 0; i  arr[j + 1]) {//如果前一位大于后一位
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交换位置
      }
    }
  }
  return arr;
}

快速排序

时间复杂度
最好的情况:每一次base值都刚好平分整个数组,O(nlogn)
最坏的情况:每一次base值都是数组中的最大/最小值,O(n2)

空间复杂度
快速排序是递归的,需要借助栈来保存每一层递归的调用信息,所以空间复杂度和递归树的深度一致
最好的情况:每一次base值都刚好平分整个数组,递归树的深度O(logn)
最坏的情况:每一次base值都是数组中的最大/最小值,递归树的深度O(n)

稳定性
快速排序是不稳定的,因为可能会交换相同的关键字。
快速排序是递归的,
特殊情况:left>right,直接退出。

步骤:

(1) 首先,从数组中选择中间一项作为主元base,一般取第一个值

(2) 创建两个指针,左边一个指向数组第一个项,右边一个指向数组最后一个项。移动右指针直到找到一个比主元小的元素,接着,移动左指 针直到我们找到一个比主元大的元素,然后交 换它们,重复这个过程,直到左指针遇见了右指针。这个过程将使得比主元小的值都排在主元之前,而比主元大的值都排在主元之后。这一步叫作划分操作

(3)然后交换主元和指针停下来的位置的元素(等于说是把这个元素归位,这个元素左边的都比他小,右边的都比他大,这个位置就是他最终的位置)

(4) 接着,算法对划分后的小数组(较主元小的值组成的子数组,以及较主元大的值组成的 子数组)重复之前的两个步骤(递归方法),

递归的出口为left/right=i,也就是:

left>i-1 / i+1>right

此时,子数组数组已排序完成。

归位示意图:

具体实现:

function quicksort(arr, left, right) {
  if (left > right) {
    return;
  }
  var i = left,
    j = right,
    base = arr[left]; //基准总是取序列开头的元素
  //   var [base, i, j] = [arr[left], left, right]; //以left指针元素为base
  while (i != j) {
    //i=j,两个指针相遇时,一次排序完成,跳出循环
    // 因为每次大循环里面的操作都会改变i和j的值,所以每次循环/操作前都要判断是否满足i= base) {
      //寻找小于base的右指针元素a,跳出循环,否则左移一位
      j--;
    }
    while (i 

参考:https://www.cnblogs.com/venoral/p/5180439.html

堆排序

堆的概念

  • 堆是一个完全二叉树。
  • 完全二叉树: 二叉树除开最后一层,其他层结点数都达到最大,最后一层的所有结点都集中在左边(左边结点排列满的情况下,右边才能缺失结点)。
  • 大顶堆:根结点为最大值,每个结点的值大于或等于其孩子结点的值。
  • 小顶堆:根结点为最小值,每个结点的值小于或等于其孩子结点的值。
  • 堆的存储: 堆由数组来实现,相当于对二叉树做层序遍历。如下图:
    堆排序是不稳定的,因为可能会交换相同的子结点。

    步骤一:建堆

    • 以升序遍历为例子,需要先将将初始二叉树转换成大顶堆,要求满足:树中任一非叶子结点大于其左右孩子
    • 实质上是调整数组元素的位置,不断比较,做交换操作。
    • 找到第一个非叶子结点——Math.floor(arr.length / 2 - 1),从后往前依次遍历
    • 对每一个结点,检查结点和子结点的大小关系,调整成大根堆
    // 建立大顶堆
    function buildHeap(arr) {
      //从最后一个非叶子节点开始,向前遍历,
      for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
        headAdjust(arr, i, arr.length); //对每一个节点都调整堆,使其满足大顶堆规则
      }
    }

    步骤二:调整指定结点形成大根堆

    • 建立childMax指针指向child最大值节点,初始值为2 * cur + 1,指向左节点
    • 当左节点存在时(左节点索引小于数组length),进入循环,递归调整所有节点位置,直到没有左节点为止(cur指向一个叶结点为止),跳出循环,遍历结束
    • 每次循环,先判断右节点存在时,右节点是否大于左节点,是则改变childMax的指向
    • 然后判断cur根节点是否大于childMax,
    • 大于的话,说明满足大顶堆规律,不需要再调整,跳出循环,结束遍历
    • 小于的话,说明不满足大顶堆规律,交换根节点和子结点,
    • 因为交换了节点位置,子结点可能会不满足大顶堆顺序,所以还要判断子结点然后,改变curchildMax指向子结点,继续循环判断。

    //从输入节点处调整堆
    function headAdjust(arr, cur, len) {
      let intialCur = arr[cur]; //存放最初始的
      let childMax = 2 * cur + 1; //指向子树中较大的位置,初始值为左子树的索引
    
      //子树存在(索引没超过数组长度)而且子树值大于根时,此时不符合大顶堆结构,进入循环,调整堆的结构
      while (childMax 

    步骤三:利用堆进行排序

    • 从后往前遍历大顶堆(数组),交换堆顶元素a[0]和当前元素a[i]的位置,将最大值依次放入数组末尾。
    • 每交换一次,就要重新调整一下堆,从根节点开始,调整根节点~i-1个节点(数组长度为i),重新生成大顶堆
    // 堆排序
    function heapSort(arr) {
      if (arr.length <= 1) return arr;
      //构建大顶堆
      buildHeap(arr);
      //从后往前遍历,
      for (let i = arr.length - 1; i >= 0; i--) {
        swap(arr, i, 0); //交换最后位置和第一个位置(堆顶最大值)的位置
        headAdjust(arr, 0, i); //调整根节点~i-1个节点,重新生成大顶堆
      }
      return arr;
    }

    完整代码:

    // 交换数组元素
    function swap(a, i, j) {
      [a[i], a[j]] = [a[j], a[i]];
    }
    //从输入节点处调整堆
    function headAdjust(arr, cur, len) {
      let intialCur = arr[cur]; //存放最初始的
      let childMax = 2 * cur + 1; //指向子树中较大的位置,初始值为左子树的索引
    
      //子树存在(索引没超过数组长度)而且子树值大于根时,此时不符合大顶堆结构,进入循环,调整堆的结构
      while (childMax = 0; i--) {
        headAdjust(arr, i, arr.length); //对每一个节点都调整堆,使其满足大顶堆规则
      }
    }
    // 堆排序
    function heapSort(arr) {
      if (arr.length <= 1) return arr;
      //构建大顶堆
      buildHeap(arr);
      //从后往前遍历,
      for (let i = arr.length - 1; i >= 0; i--) {
        swap(arr, i, 0); //交换最后位置和第一个位置(堆顶最大值)的位置
        headAdjust(arr, 0, i); //调整根节点~i-1个节点,重新生成大顶堆
      }
      return arr;
    }

    更多编程相关知识,请访问:编程视频!!

    以上就是冒泡排序、快速排序和堆排序的时间复杂度是多少的详细内容,更多请关注其它相关文章!


推荐阅读
  • 图论入门基础教程
    图论是计算机科学和数学中的重要分支,本教程旨在为初学者提供全面的基础知识。通过实例解析,如“昂贵的聘礼”问题,讲述了一个年轻探险家在印第安部落与酋长女儿的爱情故事,展示了图论在解决实际问题中的应用。教程内容涵盖了图的基本概念、表示方法以及常见算法,适合各类读者学习。 ... [详细]
  • Python进阶笔记:深入理解装饰器、生成器与迭代器的应用
    本文深入探讨了Python中的装饰器、生成器和迭代器的应用。装饰器本质上是一个函数,用于在不修改原函数代码和调用方式的前提下为其添加额外功能。实现装饰器需要掌握闭包、高阶函数等基础知识。生成器通过 `yield` 语句提供了一种高效生成和处理大量数据的方法,而迭代器则是一种可以逐个访问集合中元素的对象。文章详细解析了这些概念的原理和实际应用案例,帮助读者更好地理解和使用这些高级特性。 ... [详细]
  • WebStorm 是一款强大的集成开发环境,支持多种现代 Web 开发技术,包括 Node.js、CoffeeScript、TypeScript、Dart、Jade、Sass、LESS 和 Stylus。它为开发者提供了丰富的功能和工具,帮助高效构建和调试复杂的 Node.js 应用程序。 ... [详细]
  • 提升学习效率不仅需要正确的方法,还需要一些实用的小技巧。本文总结了多条有助于提高学习效果的建议,包括合理安排时间、选择合适的学习环境、运用记忆技巧等。通过这些方法,可以帮助学生更好地集中注意力,提高学习效率,达到事半功倍的效果。 ... [详细]
  • 本文探讨了利用Matlab平台实现同步定位与建图(SLAM)技术的研究。通过详细分析算法原理和实验验证,展示了Matlab在SLAM应用中的强大功能和灵活性。研究结果表明,Matlab不仅能够高效处理复杂的SLAM任务,还能为研究人员提供便捷的开发环境,加速算法的测试与优化。 ... [详细]
  • `chkconfig` 命令主要用于管理和查询系统服务在不同运行级别中的启动状态。该命令不仅能够更新服务的启动配置,还能检查特定服务的当前状态。通过 `chkconfig`,管理员可以轻松地控制服务在系统启动时的行为,确保关键服务正常运行,同时禁用不必要的服务以提高系统性能和安全性。本文将详细介绍 `chkconfig` 的各项参数及其使用方法,帮助读者更好地理解和应用这一强大的系统管理工具。 ... [详细]
  • Windows环境下RabbitMQ安装详尽指南
    Windows环境下RabbitMQ安装详尽指南 ... [详细]
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
  • 今天已经下载了 Visual Studio 2005 Beta 2 标准版,目前正在尝试安装,但似乎遇到了一些问题,安装未能成功。将进一步排查原因。该版本支持 .NET Framework 2.0.41202。 ... [详细]
  • 如何使用Python去除字符串中的非中文字符[Python编程技巧]
    在 Python 中,可以通过正则表达式来实现去除字符串中的非中文字符。具体方法是使用 `re` 模块中的 `re.sub()` 函数,配合正则表达式 `[^u4e00-u9fa5]` 来匹配并替换掉所有非中文字符,从而保留字符串中的中文部分。这种方法简洁高效,适用于多种文本处理场景。 ... [详细]
  • 技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告
    技术日志:使用 Ruby 爬虫抓取拉勾网职位数据并生成词云分析报告 ... [详细]
  • 将密码链接至密码输入框中以增强安全性
    在通常情况下,当TextBox的TextMode设置为Password时,直接在后台(.cs文件)绑定值到该文本框是不可行的。然而,在某些场景下,为了增强安全性,需要将密码值安全地传递到密码输入框中。本文介绍了一种方法,通过使用特定的技术手段,实现后台与前端密码输入框的安全绑定,从而提高系统的整体安全性。 ... [详细]
  • 深入理解JavaScript原型链机制与应用
    本文深入探讨了JavaScript中的原型链机制及其应用,详细解析了普通函数与构造函数之间的区别。通过实例分析,阐述了如何利用原型链实现面向对象编程,并介绍了原型链在继承和属性查找中的关键作用。 ... [详细]
  • 安装Windows 10必须使用U盘吗?如果不使用U盘,还有哪些方法可以安装Windows 10?
    安装Windows 10必须使用U盘吗?如果不使用U盘,还有哪些方法可以安装Windows 10? ... [详细]
  • 本文深入解析了HTML框架集(FRAMESET)的使用方法及其应用场景。首先介绍了几个关键概念,如如何通过FRAMESET标签将主视图划分为多个独立的区域,每个区域可以加载不同的HTML文件。此外,还详细探讨了FRAMESET在实际开发中的优缺点,并提供了具体的实例代码,帮助开发者更好地理解和应用这一技术。 ... [详细]
author-avatar
心若在梦就在_2012
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有