【一周刷爆LeetCode,算法大神左神(左程云)耗时100天打造算法与数据结构基础到高级全家桶教程,直击BTAJ等一线大厂必问算法面试题真题详解(马士兵)】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358
目录
2、认识O(NlogN)的排序
2.3 快排QuickSort
2.3.1 快排1.0
2.3.2 快排2.0
2.3.3 快排3.0
2.4 堆排序
2.4.1 heap-insert过程
笔记:
2、认识O(NlogN)的排序
2.3 快排QuickSort
情况1:给定一个数组arr和一个属num让小于等于num的元素都位于它左侧,大于num的数都在数组右侧。要求额外空间复杂度O(1),时间复杂度O(N)。
解法:arr[i]<=num,arr[i]和L区的下一个交换。L区右扩;arr[i]>num,i++;
情况2:给定一个数组arr和一个属num让小于num的元素都位于它左侧,等于num的数在数组中间,大于num的数都在数组右侧。要求额外空间复杂度O(1)、时间复杂度O(N)。
解法:
arr[i]<num,arr[i]和L区的下一个交换。L区右扩;
arr[i]==num,i++;
arr[i]>num,arr[i]和R区的上一个交换。R区左扩;
2.3.1 快排1.0
取最右侧的数,把它左侧的数分为小于它的左区域和小于它的右区域,然后再把它和右区域的第一个数交换。再分别对左区域和右区域执行相同的操作。
【Q1:分治和递归的区别?
A1:二者是不同维度的概念。递归是程序的实现方式,是程序调用自身;分支是一种算法,核心思想是将父问题拆分为多个无重叠的子问题。逐个解决每类子问题后,合并子问题的解,得到父问题的解。分治可以用递归实现。】
2.3.2 快排2.0
取最右侧的数,将左侧的所有元素按“小于区域”“等于区域”“大于区域”排列,然后再把它和“大于区域”的第一个数做交换。
优于“快排1.0”是因为它固定下来了“等于区域”,移动其他元素时不用再移动这部分。
快排1.0和2.0的时间复杂度都是O(N^2)。性能最好的情况,是左右两侧等规模地不断进行二分,时间复杂度为O(NlogN)。
2.3.3 快排3.0
随机选一个数作为划分参照物,把它和最右侧的元素交换。由于数是随机选的,所以处于每个位置上的概率都相同,为1/N。因此把所有可能的master公式求概率相加后再求数学上的长期期望,得到O(NlogN)。
综合来看,快排3.0由于是随机选数所以时间复杂度最接近O(NlogN)。
2.4 堆排序
把数组转化为完全二叉树的话,一个节点的左孩子是arr[2i+1],右孩子是arr[2i+2],父节点是arr[(i-1)/2]。
堆是完全二叉树,分为大根堆和小根堆。大根堆是在这个完全二叉树中,每一棵子树的根节点都大于树上的所有节点。小根堆反之亦然。
2.4.1 heap-insert过程
若不断有新的数加入,如何维持大根堆:“heap-insert”过程。如果子节点大于父节点,直接交换该节点arr[i]和父节点arr[(i-1)/2],不断和父节点比较,如果父节点比当前节点大或已经抵达了根节点,停止交换。小根堆也相似,不断让比父节点小的值和父节点交换。
如果用户要获取并移除大根堆中的最大值,该怎么维持大根堆:用最新加入的值替换掉最大值(根节点),heapSize-1,先比较再交换,直至变成大根堆。