算法day05 master公式估算递归时间复杂度 归并排序 小和问题 堆排序

2.认识O(NlogN)的排序_哔哩哔哩_bilibili

         master公式

        有这样一个数组:【0,4,2,3,3,1,2】;假设实现了这样一个sort()排序方法,

将数组二分成左右两等分,使用sort()对左右两个小数组进行排序,就满足master公式的使用;

或者将数组平均分成三等分,n等分,都满足master公式。



      归并排序

                  

 小和问题

        原数组一分为二,左数组内部求和,右数组内部求和,左右数组比较求和,将三部分小和相加求和。

        左数组内部求和,右数组内部求和的过程就是原数组一分为二小和相加求和的过程。

        问题一:

                定义一个左边界,左指针

                遍历数组,从数组第一个元素开始比较:

                        如果比num值大直接跳过,

                        如果比num值小将边界长度+1,指针右移1位

                直到下标越界,就实现了遍历一遍整个元素时间复杂度o(n),空间复杂度0(1)

        问题二:

                定义一个左边界,左指针,右边界,右指针;

                从数组第一个元素开始比较: 默认先调用左指针

                        如果比num值大将右边界长度+1,右指针左移1位,调用右指针

                        比num值小将左边界长度+1,左指针右移1位,调用左指针。

                直到左右指针相遇。

                



        堆排序

                  通过堆排序算法实现将给定的数组元素按大小构建一个完全二叉树,并且二叉树分为最大堆和最小堆两种类型。

                  最大堆每颗树的父节点是当前树的最大值或者最大值之一;

                  最小堆每棵树的父节点是当前树的最小值或者最小值之一。

                heapify()

                heapinsert()

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 21:24:02       141 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 21:24:02       156 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 21:24:02       129 阅读
  4. Python语言-面向对象

    2024-07-20 21:24:02       141 阅读

热门阅读

  1. Python正则表达式

    2024-07-20 21:24:02       26 阅读
  2. 【SpringBoot】SpringAOP实现公共字段自动填充

    2024-07-20 21:24:02       25 阅读
  3. Netty的线程模型是怎么样的

    2024-07-20 21:24:02       24 阅读
  4. python入门教程,小白10分钟快速入门

    2024-07-20 21:24:02       27 阅读
  5. 【Webpack】HMR 热更新

    2024-07-20 21:24:02       25 阅读
  6. Fisher-Yates 算法-数组元素随机交换

    2024-07-20 21:24:02       32 阅读
  7. C++ 中值传递和引用传递的区别?

    2024-07-20 21:24:02       24 阅读
  8. MATLAB的基础知识

    2024-07-20 21:24:02       28 阅读
  9. 【Vue】vue2 vue-awesome-swiper 刷新无法自动滚动解决

    2024-07-20 21:24:02       27 阅读
  10. 【Go系列】模块和协同开发

    2024-07-20 21:24:02       27 阅读