数据结构笔记39-48
碎碎念：想了很久，不知道数据结构这个科目最终该以什么笔记方式呈现出来，是纸质版还是电子版？后来想了又想，还是电子版吧？毕竟和计算机有关~（啊哈哈哈哈哈哈哈）
概率论已经更新完了，不出意料的话，六月末七月初会更新电子技术基础，七月中旬更新计算机组成原理
数据结构45-4分钟搞定堆排序_哔哩哔哩_bilibili
39-48
目录
排序算法
直接插入排序
折半插入排序
编辑
希尔排序
快速排序
简单选择排序
堆排序
插入元素：
删除元素：
归并排序
基数排序
排序算法
直接插入排序
操作流程：
选取19（它是第一个数），并将其作为有序序列
第一轮：
选取35，
并与有序序列（也就是19）进行比较，
35>19，
于是在19的后面。
这样，19和35组成有序序列
第二轮：
选取9，
并与有序序列（也就是19，35）进行比较，
9<35
9<19
于是9放在19前面。
这样9，19，35组成有序序列
第三轮：
选取2，
并与有序序列（也就是9，19，35）进行比较，
2<<35
2<19
2<9
于是2放在9前面。
这样2，9，19，35组成有序序列
以此类推，得到最后结果
折半插入排序
具体看这一步，如何安置15
1.将15放到初始位置，也就是0的位置
2.low指向第一个元素
3.high指向15原来的位置
4.mid=（1+6）/2=3.5 取3，所以指向3的位置
5.15和17进行比较，15<17
6.high=mid-1,high指向2的位置
7.mid=（1+2）/2=1.5 取1 所以指向1的位置
8.15和2进行比较，2<15
9.low = mid+1，low指向2
low和high相等的时候结束了。所以15插入到后面
这些是另外一种思考方式，因为长课程那里的high不是指向元素15，而是指向元素35。
10.mid=（2+2）/2 ，mid指向2
11.15和2比较，15>2
12.low=mid+1
13.low>high,退出循环
希尔排序
1.间隔分组，这里有8个，因为为总长度的一半，因此为4组
2.进行组内排序
7<19
22>15
23<25
17>9
3.再分组，为之前的一半，之前是4组，现在两组
3.进行组内排序
4.再分组，之前是2组，现在就1组
5.组内排序
冒泡排序
比较次数：数组元素-1
7和22进行比较
22和23进行比较
23和17进行比较，需要交换
23和19进行比较，需要交换
23和15进行比较，需要交换
最终23被确定，因此第二轮23不需要参与比较
7和22进行比较
22和17进行比较，需要交换
22和19进行比较，需要交换
22和15进行比较，需要交换
最终22被确定，因此第三轮22不需要参与比较
以此类推
快速排序
1.选取中心轴，一般为首位，这里是元素19 
2.移动high指针，25>19,high指针继续移动，23>19,high指针继续移动，15<19,15拿出来，放到19原本的位置（0索引位置）
3.移动low指针，9<19,7<19,17<19
5.当low=high时，中心轴被确定
第一轮排序结束
第二轮：会分别产生两个low，两个high，缩小范围，以此类推进行排序
简单选择排序
1. 在一堆数中找到最小的，13，然后与第一位进行交换
2.在一堆数中找到最小的，27，然后与第二位进行交换
以此类推
堆排序
我们调整的是大根堆，所以会把最大值放在根节点，且父节点会大于子节点
8/2-1，所以从3号位置开始调整
97>57，不用调整。
3号调整完了，就调整2号。
2号的父节点大于子节点，因此不用调整。
2号调整完了，就调整1号。
父节点小于子节点，因此取子节点中最大值放在1号位，也就是1，3号位置进行交换
1号调整完了，调整0号节点
父节点大于子节点，因此0，1号位置进行交换，
再看一眼，1号节点小于其子节点，因此将1，4号位置进行交换
最后，根节点为最大值，并且所有的父节点都大于其所拥有的子节点，即算完成
（这里的38和57还要对换一下）
插入元素：
插入85
只需要沿着这个根进行调整就好
85>38,85>76
删除元素：
删除堆顶元素97
将最末尾的38放在堆顶，将97拿出来，然后从上到下进行调整
对换的原则是要使得父节点大于子节点
38和其子节点相比，85更大，85和38进行对掉
38和76对掉
38和57对换
归并排序
两两进行比较，7和22，23和17，19和15，25和9
然后再进行7和22和23和17的比较，19和15和25和9的比较
最后进行7和22和23和17和9和15和25和9的比较
基数排序
第一轮，按个位排
第二轮，按十位排
第三轮，按百位排，第三轮就是最后结果
