Day4 25/2/17 MON
【一周刷爆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，先比较再交换，直至变成大根堆。