ShoelessCai - 408 | 数据结构排序

408 | 数据结构排序

- 2024 -
02/18
19:44

零号员工

发表时间：2024.02.18 作者：Jingyi 来源：ShoelessCai 阅读：147

我们考虑到用户体验，以及版权问题。用户对于计算机拥有进一步探索诉求的，我们推荐京东的购买渠道，点击文轩书店王道考研复习指导。

Pre Talk

Again，您自己都无法增长，就别提“帮助别人”，第一要义。

关于商业业态，什么样的业务合适用资本刺激？CEO 具体做点啥？收乐财算是自媒体吗？Jingyi 怎么定位这家公司？且听我们娓娓道来。

BTW，我很神经地将这篇演讲练习，加入了《自我训斥集锦》。

01 查找分类

7.1

第一节，主要知识点直接插入排序、折半插入排、希尔排序。

直接插入排序，Jingyi 会给它一个名词“整理手牌”。按顺序取数据，排序着插入。

折半插入排序，两端设置 low, high, mid = (high+low)/2，中间指针的元素值 > 高指针（high）的元素值，则 high = mid - 1；然后，中间指针的元素值 <= 低指针的元素值， low = mid + 1。

希尔排序，基本思想是，不断抽取子列排序再放入。

习题笔记

1.直接插入排序，比较次数 n(n-1)/2。验证方式，即元素个数为 1，元素个数为 2，元素个数为 3，代入验证。一定要学会交叉验证。

2.冒泡排序扫面一行，一定会有两个元素位置归其位，且一定是大元素在右边，小元素在左边。直接插入排序，会出现小元素对在右边。

3.插入排序，可能存在一种情况，即最后一次排序之前，所有元素都不在其位置。例如，612345。

4.希尔排序考察增量，主要考察哪些元素变换位置了，梳理共同点。

5.折半插入，时间复杂度 O(n2)，这里是依据物理存储结构的。

6.希尔排序没有“归位”功能，即排序之后，没有元素归到其位置。

7.2

讲课

1.插入排序比较次数 = n(n-1)/2

2.希尔排序是插入排序的一个子集。

综合-1：关键词序列{4，5，1，2，6，3}，写出直接插入排序。

第一轮：4 | 51263
第二轮：45 | 1263
第三轮：145 | 263
第四轮：1245 | 63
第五轮：12345 | 6
第六轮：123456

注意，顺序取一个元素，排序。每个元素O(n)，共 n 个元素，时间复杂度 O(n2)。

综合-II：给出关键字序列{50，26，38，80，70，90，8，30，40，20}，增量分别为 5，3，1的时候，排序结果。

解答：

原始序列 50，26，38，80，70，90，8，30，40，20

（1）增量为 5。50，8*，30*，40*，20*，90，26*，38*，80*，70*

（2）增量为 3。26*，8，30，40*，20，80，50*，38，90，70

（3）增量为 1。8，20，26，30，38，40，50，70，80，90

7.2 讲课 Ending

7.3

本节主要聚焦于“冒泡排序”和“快速排序”。

1.算法介绍

冒泡排序，每一行两个相邻元素相互位置互换。

快速排序，高低指针，和中间指针，如果高指针数值小于中间指针数值，则与低指针互换。

两个算法时间复杂度都是 O(n2)。

快排，一定有一个元素“归位”。

关注两种说法，移动元素次数，比较趟数，概念不一样。移动元素次数，即排序过程中，移动元素的次数。而比较趟数，为了排序，对比多少次。

2.练习知识点

快速排序 + 顺序列表（数组）。据说最佳组合。
快速排序，针对的序列最好随机性较高，如果序列已经基本有序，快排性能未必那么突显。
排序全过程在内存的，称为“内部排序”。内部排序算法，平均性能最好的，快速排序。
排序有部分要存到外存，称为“外部排序”。
对于快速排序而言，如果进行了 2 次以上。序列是两边有序。
快速排序，中间值（pivot） matters a lot. 如果 pivot 接近数列中间的元素值，则速度快；如果 pivot 接近数列的最大、最小值，则排序速度慢。
快排扫一次一定会有个元素归位，如果 2 个元素归位，则扫了两次。
快排的递归次数，与每次划分之后，分区处理顺序无关

知识点及练习

7.4

本节是“简单选择排序”，“堆排序”。

选择排序，选 + 排。选的时候，选出最小或者最大的，排就是直接放在某个元素之后。

堆排序，通常都是自下而上进行交换。

本小节的习题，有很多涉及，已知一个序列，是否能判断是不是完全二叉堆，Complete Binary Heap。

怎么判断呢？遵从以下原则：

第一，必须是完全二叉树 CBT；

第二，每个子树必须满足完全二叉堆。例如，小根堆要保证左右孩子必须大于父母节点；与此同时，大根堆要保证左右孩子必须小于父母节点；

案例-1：序列 {19，34，26，97，56，75}

按照层次遍历：

案例-2：序列 {15，9，7，8，20，-1，7，4} 建立小根堆。

这里要注意，二叉堆建立起来之后，一律用层次遍历顺序表示。

案例-3：关键码序列{23，17，72，60，25，8，68，71，52}，两次排序之后，余下的序列

{ 23，25，68，52，60，72，71 }

注意

小根堆、大根堆，整个顺序可以不一致，但是子树（3个节点）内部，一定满足小根堆、大根堆的定义。

【2009】关键字序列 {5，8，12，19，28，20，15，22}小根堆，插入关键字 3 ，调整之后的小根堆是（）

插入新的关键字 {3} 之后，得到：

3，5，12，8，28，20，15，22，19

解析：

关键字插入是在叶子层面，从最底下的子树开始按照小根堆的定义，将两个节点的值互换。

【2011】已知序列 {25，13，10，12，9} 是大根堆，在序列尾部插入新元素 18 ，将其再调整为大根堆，调整过程中元素之间进行比较次数（）

解析：

进行比较 2 次，分别是原序列中的元素值 10 节点，和原序列中的元素值 25 节点。

【2015】已知小根堆 8，15，10，21，34，16，12 ，删除关键字 8 之后，重新建堆，关键字的比较次数（）

解析：比较 3 次，分别是 10，15，16，只有对比 10 节点的时候，是换的。

【2018】将数据序列 {6，1，5，9，8，4，7} 建成大根堆，正确序列的变化过程。

答案：

6，1，7，9，8，4，5 ->

6，9，7，1，8，4，5 ->

9，6，7，1，8，4，5 ->

9，8，7，1，8，4，5

练习

平时的订正

7.5

这部分工作我在自己居住的地方完成的，由于上次室友投诉我外放新闻的问题，加上闹钟问题，永远都是所到之处，和伙伴们的主要冲突。

其中，有些冲突我会处理，有些不会。总而言之，非常感谢冲突，这些事件，相较于某些高防御、低输出的工作环境，真的是显得真实许多了。

然而，我并不鼓吹沟通的时候，完全“简单粗暴”。我倒是追随学习得到的课好几年，以前不明白的事，你听课，反复听，骨灰级听，也能听懂。那就是，大多数情况，是油光水滑效率高些，虽然油光水滑有其副作用，但是大多数时候，相互之间能够理解对方部门一些，稍微动点小脑筋，把各部门说服的方式，比较效率。

什么时候不管用？

大概当你感谢冲突的时候，可能得自己自发主动地思考，是不是应该调整一下组织内部的情况。当然，这些略显纸上谈兵了，具体还是要实践。