数据结构笔记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的比较 

基数排序 

 

第一轮，按个位排 

 第二轮，按十位排

第三轮，按百位排，第三轮就是最后结果