少儿编程算法
第二集 认识O(NlogN)的排序
1 用递归方法找一个数组中的最大
2.认识O(NlogN)的排序 P4 - 03:28
问题：
函数实现方式：
此段代码中的mid = L + ((R - L) >>1)是为了计算L与R范围内的中间值。传统的方式是通过(L + R)/2来实现这一目标。然而，在某些情况下（例如当L + R可能会导致数值溢出时），这种直接的方法可能会出现问题。因此，在这种情况下推荐使用L加上(R - L)的一半来代替（即L + (R - L)/2）。值得注意的是，在这种替代方法中（即(R - L)/2），由于我们避免了直接相加可能导致的溢出问题，并且可以通过位运算中的右移一位操作来高效地进行计算（即相当于取整除以二的操作）。
递归调用过程：
递归调用时间复杂度：
b相当于表示了相同规模的递归；a相当于表示相同规模下递归调用发生的次数；d相当于表示在不包括子过程的情况下其余过程中所花费的时间复杂度。
在满足特定条件下进行递归调用过程时，在包含a次等量b的操作的情况下，则可以通过该master公式直接计算时间复杂度。
2 归并排序
2.认识O(NlogN)的排序 P4 - 35:00
问题：
算法图解：
代码实现：
Process是递归过程
merge过程把左边右边合并到一起
注意：
或许会感到疑惑的是，在process递归调用的过程中。当递归深入至最底层时，在此阶段仅涉及两个数。然而，在这一过程中确实存在一个merge过程（即合并与排序这两个步骤），最终能够生成一个全局有序数字。
merge的算法：
时间复杂度：
符合master公式
递归process符合2倍等量N/2的递归操作
merge的时间复杂度为N，两个指针分别往左移
算出来也是O(NlogN)的复杂度
3 小和问题
2.认识O(NlogN)的排序 P4 - 01:01:34
问题：
算法图解：
暴力求解：
巧妙解法，节省时间复杂度：
求右边有多少个数比此数大，以此求小和，可以用归并排序求出
最终结果:
代码：
左组排序要求小和
右组排序也要求小和
左右merge到一起也要求小和
所有小和的总和就是小和的最终结果
merge的时候怎么求小和？
4 逆序对问题
2.认识O(NlogN)的排序 P4 - 01:29:03
问题：
算法图解：
事实上是求右边有几个比当前数小，属于merge改写的题目
5 荷兰国旗问题
2.认识O(NlogN)的排序 P4 - 01:44:26
问题1：小于num放左边，大于num放右边
问题2：荷兰国旗
问题1图解：
首先制定一个“小于等于区域”，指针代表此区域的"右边界"
当i指针指向的数值不大于设定值num时，则与位于该区域紧邻的一侧的位置进行交换；该区域随之扩大以包含这次交换过来的数据，并将指针向后推进一位继续检查
问题2图解：（荷兰国旗）
指定小于 大于 等于区域
若i值低于num，则将小于区域下一位置进行交换；当i等于num时保持不变；若i高于num则与大于区域前一位置互换，并需注意这一变化应立即与num进行对比以确定下一步操作
6 快速排序问题
2.认识O(NlogN)的排序 P4 - 02:02:10
快排1.0：
在数组中 ，将num参数设置为数组末尾元素值作为对比基准 。然后借鉴问题一中的排序方法完成如上所述的操作
将小于等于nu的部分放置于左侧区域，并将大于等于nu的部分置于右侧区域。
随后，在右组中将末尾处放置参考数值于首位位置。
这一步骤之后，则能确保整个数据集被划分为三个区间：<=nu、nu以及> nu这三个区间；其中中间区域nu无需再次处理。
接着，在处理完上述步骤后，在处理完中间区域后的两个子区域内再次应用这一方法。
通过逐步递归地执行这些步骤，则可以最终获得一个有序排列的结果。
快排2.0：
基本理念是运用荷兰国旗的原理
核心理念即采用荷兰国旗「双向」算法将区域划分为三个部分然后左右两侧各自再进行递归处理具体而言则可参考荷兰国旗算法
在如下图所示的情况下，在最后一层递归中固定位置1的位置，在此情况下数字0仅剩一个无需进一步递归的情况还需要完成一次排序操作
总结快排1&2：
快排1分别采用了问题1的方法进行处理,快排2则采用了问题2的技术策略进行优化
在数据分布较为理想的情况下,算法的表现更为出色；但在极端情况下则会面临性能瓶颈
相反地,当输入数据分布较为均匀时,算法能够发挥出最佳性能
快排3.0：
从给定的数据集中随机选取一个元素，并将其与尾端的数值互换位置；随后应用快排算法（版本号为2.0）的过程。经过上述步骤后，在上述分析中提到的好案例与坏案例具有发生概率。由此所述的算法其时间复杂度期望值为O(N log N)
快排3.0代码：
从区间L到R中随机选取一个数与R交换位置，在此过程中使用选出的数字对区间L到R进行partition分割。其中int[] p = partition(arr, L, R)返回值为2，则表示分界线位于p(0)和p(1)之间。该算法即为著名的荷兰国旗算法。
第三集 详解桶排序以及排序内容大总结
1 快排的空间复杂度：
接着上一集的内容，如果在上述讲到的最差情况下，空间复杂度为O(N)：
如果在好情况下，空间复杂度为：O(logN)
然而三种情况均符合概率分布模型，在整体上来说其空间复杂度将趋近于O(\log N)水平。
2 一个连续的数组->完全二叉树
一个从零开始连续排列的数组遵循完全二叉树的索引规则，在这种结构中基于父节点的索引位置即可确定其左子节点和右子节点的位置。通过左子节点的位置同样能推导出其父节点的位置。具体计算方法请参考附图中的公式说明。
IMPORTANT: 堆结构就是用数组实现的完全二叉树结构
3 堆的两个重要的操作
heapinsert
heapfy
3.1 大顶堆的定义
每一棵子树的“头”都是最大值
3.2 heapinsert从堆底往堆顶操作:
Step1: 右孩子需要和父进行比较，如果比父大，则进行交换，变成大顶堆：
->
Step2:
插入的值，不断与父进行比较和替换形成大顶堆的形式：
->
->
总结规律：每当插入一个值时,该值会与其父节点反复比较,若该值大于其父节点则替换上层节点；break条件分为两种情况:一是到达顶层节点；二是该值不再大于其父节点,则算法终止；通过上述操作可确保每一步插入后的结构均为最大堆形式
实现代码：
如果当前数大于父的值，则和父做位置交换。
交换停止条件：到达堆的头位置 or 不再比父大，则可以停止
3.3 heapfy堆化，从堆顶部往底部操作
3.详解桶排序以及排序内容大总结 P5 - 30:11
heapfy
问题1：为了解决该问题，请先符合大顶堆的要求，并取出其中的最大值元素；确保剩余的数据仍然构成一个有效的最大值堆结构。
Step1:
返回堆头的数值6，即为堆的最大值.
Step2:
移除堆顶元素，并将其替换为从队列中获取的新值。同时令队列长度减少一位，并使队列中索引为5的位置上的数值将不再有效。
->
以起始节点值4为基础，在其左右子节点中选取较大的子节点数值5与之对比。若该较大子节点值比当前节点值增加4，则执行替换操作。
当交换完成后不再存在左子节点或右子节点，并且两个子节点的最大值均小于当前节点的值时
实现代码：
除了从0位置往下做heapfy，可以从任意位置往下做heapfy：
先判定左子节点索引是否越界？（其实质即是确认是否存在左子节点）
表明left+1<heapsize表示该节点存在右子节点，并且右子节点的数值大于左子节点的数值，则最大的元素索引即指向右子节点；否则，则指向当前父节点索引
比较父节点与较大子节点之间的数值大小后确定最大元素索引
检查最大元素索引是否等于当前循环到达的父节点索引；如果是，则无需继续向下遍历；如果不是，则需将最大元素索引与当前父节点索引进行交换
将最大元素所在位置的索 引赋值给当前父节点变量index之后继续向下执行判断操作
3.详解桶排序以及排序内容大总结 P5 - 45:22
任意抽调i位置的数，保证堆
问题2：如果任意改掉 i 位置的数，依旧保证是大顶堆形式。
判断i位置的数值相比之前是变大 还是 变小了？
变小：往下heapfy
变大：往上heapinsert
堆操作的复杂度
3.详解桶排序以及排序内容大总结 P5 - 47:16
复杂度介绍
完全二叉树的高度
heapinsert / heapfy的复杂度: O(logN)，N代表已经有的个数。
4 堆排序
3.详解桶排序以及排序内容大总结 P5 - 50:51
堆排序
Step1：数组->大顶堆heapinsert
给定的原始数组：
变完之后的大顶堆：
总结：为了对给定的数组进行排序，在第一步需要将该数组构建成大顶堆的形式。整个过程采用heapinsert方法逐步将每个元素插入到合适的位置上，并使整个结构始终保持为一个有效的最大值堆。同时使用heapsize方法统计并确定当前的大顶堆中元素的数量情况。需要注意的是，在完成一次完整的heapinsert操作之后，在该数组的第一个位置必定会放置最大的值，并以此为基础奠定了后续操作的基础
Step2：对数组进行排序heapfy
3.详解桶排序以及排序内容大总结 P5 - 55:09
对数组进行排序
首先进行数组末尾与首位元素的互换操作。（根据第一步heapinsert过程所得结果，在原始数组中首位元素必然是该数组中的最大值）随后降低堆大小（heapsize--），使最后一个元素被固定不再参与后续堆的操作
从堆顶位置执行heapify操作以形成大顶堆结构的同时，并需对数组中的数值进行交换
- 继续依次将数组第0位及第5位的数值进行互换，并反复执行前面所述步骤1至2的操作。直至heapsize降至零时，则最终即可获得一个已按顺序排列好的数组。
实现代码：
3.详解桶排序以及排序内容大总结 P5 - 01:02:37
堆排序代码
Line12: for循环把数组变成大顶堆的形式
Line16: 0位置和最大的位置上的数进行交换，交换玩之后heapsize–
Line17: 堆的大小只要没有减为0，周而复始进行heapfy的操作
堆排序复杂度：
3.详解桶排序以及排序内容大总结 P5 - 01:05:01
堆排序时间复杂度
在排序过程中涉及到了heapinsert和heapify操作。其时间复杂度为O(N log N)，其中N代表数组中元素的总数量。
空间复杂度：O(N)
Bonus:
1 第一步把数组变成大顶堆的过程有一个时间复杂度更低的办法：
将数组元素按顺序构建为一个完全二叉树结构。随后通过自底向上的方式，在从右至左、由下而上的位置上执行heapify操作来维护大根堆特性。
2 时间复杂度：O(N)
3 实现代码：
从末尾位置开始，在堆结构中自底向上的最右边到左边进行heapsort操作，则能够构建出最大堆结构。
5 堆排序扩展题目
3.详解桶排序以及排序内容大总结 P5 - 01:19:44
堆排序扩展题目
问题：
算法图示：
首先将数组中的0至6号位置上的七个数字利用heapinsert方法构建一个小根堆。
随后取出小根堆的堆顶元素（即当前数组中0至6号位置数值最小的那个值）并将其放置到数组索引0的位置。
接着将数组第7号位置的元素插入到小根堆中。
再次取出当前小根堆中的最小元素（即此时整个数组中1至7号位置数值最小的那个值）并将其放置到索引1的位置。
不断重复上述操作即可使整个数组逐步有序排列。
在每次循环过程中每个元素移动的距离都不会超过k=7。
时间复杂度：O(N·logk)，其中k代表每次移动的最大可移动距离；N表示数组元素的数量
实现代码：
Line11: 先把数组中的前k个数放到小根堆里去
从数组中取出一个元素放置于队列头部，并将该元素同时加入到小根堆（优先队列）中去。反复执行上述步骤。
数组中不能再加入更多数字了，请取出小根堆中剩余的所有元素
注意：此方法主要依赖于小根堆的插入与弹出操作。当执行这些操作后，默认算法会将数值进行自动排序。因此我们无需关心具体的heapinsert或heapify函数实现细节就可以完成相关操作
6 比较器的使用
比较器的定义：
例子：
147行进行sort的调用
仿函数在52行
在堆里的使用：
第26行，堆的默认是小根堆，加上仿函数AComp实现大根堆功能
大根堆实现的仿函数（第9行）：
综上所述，在C++中仿函数功能允许开发者创建较为复杂的比较策略；具体实现细节可参考关系仿函数的相关介绍：https://www.bilibili.com/video/BV1et411b73Z?p=241。
7 不基于数值比较的排序案例：奇数排序
3.详解桶排序以及排序内容大总结 P5 - 01:58:27
奇数排序
问题：对以下数字进行排序：
具体步骤：
确定最大数值的位数后，在剩余数值前补零以达到一致长度
创建多个 bucket（每个 bucket 代表一种类型的数据存储空间）
根据个位数值将相应的数字分配到对应的 bucket 中：
按照桶的顺序，再把数字重新倒出来：
接下来按照十位数的数值，把数字分别放入桶内：
然后再把桶内数据倒出：
最后按照百位数进桶再倒出，和上述方法一样：
算法图解：
通过代码来实现上述出入桶算法时，运用的如下的方式：
count数组（也称桶）用于统计原始数据集中各个元素出现次数；其中每个下标对应一个特定的数据值；而其内部元素则记录着相应数据值出现的具体数量；为了实现数据的有效组织和快速查询；我们引入了一个辅助配平数组；其与原始数据量级相仿
将count数组进行处理后得到结果如下：它所代表的意义是对各个位数上的数字出现次数进行了统计记录。其中062号位的数字出现次数被记录下来
从右往左将原数组中的数字转移到help数组中的指定位置，并最先处理
062：在count数组中统计各位小于等于2的数量为4个；由于从右往左依次处理元素
且需要对count数组中各位小于等于2的位置进一步减少其计数至3
以此类推得到如下结果：
代码实现：
对数组arr中的区间[L, R]进行排序
maxbits = digit代表该批数字的最大十进制位数
该算法在处理过程中需要依次将数值放入桶中digit次
为了容纳所有可能的十进制位数值（0至9），计数器初始化为一个长度为10的数组
其中d(digit)表示当前处理的数字位数：当d=1时对应个位数；d=2时对应十位数；以此类推
我们统计每一位上的数字出现的情况：count[i]记录的是各位上出现i的具体数值的数量
通过累加操作生成小于或等于当前阈值j的数量统计
算法从右向左遍历原始数组以完成数据转移至辅助数组bucket的任务
将辅助数组bucket中的数据逆序放置回原数组arr，并进入后续计算步骤