算法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()