[数据结构与算法]数据结构与算法——左程云04

【前言】：

后续有时间会将文中的图片部分，以及手写笔记中的过程图制作成JPG图片上传。

【1】：排序算法的稳定性

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-39Zpthxz-1663993781844)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819002401916.png)]

目前没有找到时间复杂度 O（N*logN） , 额外空间复杂度O（1），而又稳定的排序。

【理解稳定性】：

• 《@@40_1》

稳定性是指排完序后，相同的元素的次序是否仍然能够保证。

排完序后，能否将原先的相对次序给维持下来～～～

若能够保证值相同，元素在排完序后的顺序，则说明这个算法是有稳定性的，否则是认为没有稳定性的。

【稳定性的作用】：

如果排的是基础类型的数组，稳定性是没有用的。

基础类型数组，稳定性毫无作用。

//非基础类型中稳定性还是非常有用的。

• 非基础类型才有用～～～

【举例证明稳定性的作用】：

【学生】：

• 《@@40_2》

学生有两个属性——age 、class .

【总结】：

如果两轮排序均是稳定的话，则会出现——在各个班级内部学生的年龄都是从小到大排的。

【商品】：

• 物美价廉

先按照价格从低到高 ， 再按照好评率从高->低 ， 如此一来，若次序能够保留的话，便能得到性价比较高的商品。

//非基础类型中稳定性还是非常有用的。

【经典排序算法的稳定性探讨】：

【选择排序】：

• 《@@41_3》

无法；

【冒泡排序】：

//可以的；

相等的时候不交换 ， 故前面的数未跑到后面 ， 保证了有序性。

【插入排序】：

//可以的；

右边的数不比左边小，让其停在那个位置，即能保证有序性；

【归并排序】：

//可以的；

关键在于你merge的时候如何merge???

• 《@@41_4》

【小和问题】：

小和问题相等时，是先拷贝右边的，所以小和问题丢弃掉了稳定性；

【快速排序】：

无法；

partition的时候就做不到稳定性；

• 《@@41_5》

【堆排序】：

无法；

堆排是根据自己堆上的那颗完全二叉树来调的。

//首先要将整个数组变成大根堆——这一步就破坏了稳定性！！！

• 《@@42_6》

【计数排序&基数排序】：

//均可以做到稳定性～

我入桶和出桶的顺序是可以维持的。（ 先入桶的我就先出桶 ）

【总结选择排序算法】：

【首选排序】：

一般先用快排（V3） ， 经过大量数据测试，快排是最快的（ 因为它的常数项最小 ），常数项低，跑得最快·

【对空间有要求】：

堆排；

【需要使用到稳定性】：

归并排序；

【排序算法时间复杂度总结】：

• 《@@42_7》

【2】：排序算法常见问题

【Q1】：

基于比较的排序能否做到时间复杂度在O（NlogN）以下？

//目前来讲没有找到。

【Q2】：

时间复杂度在O（N * logN）的程度上，空间复杂度能否降到 O（N） 以下呢，并且还能保持稳定？

//目前为止，未找到这样的排序。

【常见的坑】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d2PMibkI-1663993781845)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819115106314.png)]

（1）：

归并排序内部缓存法，可以使额外空间复杂度变成O（1），但是变完之后，就不再稳定了！！！

//这就不如直接用堆排序；

（3）：

做到的同时，空间复杂度会到 O（n）的程度，所以不如直接用归并排序。

“01 stable sort” 是一篇冷门论文 ， 其学术地位并没有多么重要。

【面试大坑题】：

数组是整型数组，每个位置的值不是奇数便是偶数，奇数放到数组左边，偶数放到数组右边，还要求奇数间的次序保持不变，偶数间的次序也保持不变；要求额外空间复杂度O（1），时间复杂度O（N）。并且：原地的，不使用辅助数组。

• 直接怒怼面试官！！！

这个问题 <==> 快排partion中的 0、1标准～ ～ ～

【工程上对排序的改进】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JRXFCWhB-1663993781845)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819123455724.png)]

【36:12】：

• 具体代码讲述这种改进。

if( l==r ){
  return;    //直接不排了。
}

if( l > r-60 ){    // L～R范围上，其样本量是小于60的。
  在arr[l~r] 上插入排序；  // o(N^2) , 小样本量的时候，跑得快～～～！！！
  return;
}

【分析】：

大样本量的时候，快速排序；

小样本量的时候，使用插入排序。（ 小样本量时，常数项低 ）

O（N^ 2） 小样本下，瓶颈不明显。

• 综合排序，利用各种排序算法的优势。

【Arrays.sort（）内部 】：

• 基础类型

//使用快排～

• 非基础类型（自定义的类）

//归并排序～

【解释】：因为稳定性

• （基础）

对于基础类型来说，稳定性无用，故使用常数时间较低的快排～

• （自定义类）

保持稳定性（ 万一用户要用到稳定性呢？？？ ）

【3】：哈希表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nLGnCs0U-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819130014214.png)]

【 HashSet、HashMap 】：

在内部结构上是没有区别的，无非是有无伴随数据（ value ）罢了。

[ hashMap.put( ) ]:

更新的是Value； //通过put可以完成加入/更新。

【哈希表的时间复杂度】：

不论多少条记录 ， CRUD的时间复杂度都是常数级别的。

• 而且和数据量无关～

//有关哈希表的常数时间还是比较大的。

【按值传递 & 引用传递】：

• （1）Key是基础类型 ， 如Integer、String

会把KEY拷贝一份，然后把Value给对应上～

//内存占用这个东西的大小；

//好像——KEY、VALUE都是按值传递！！！

• (2) Key是自己定义的类型：

如KEY是Student类型时，KEY一律是8个字节（内存地址），将内存地址拷贝一份放到KEY里；

//内存占用这个东西内存地址的大小；

【按值传递 & 引用传递】：

• 按值

传给参数的是一个新的变量，和原变量没关系了；

• 按引用

传过去之后还能进行修改～～～

【4】：有序表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iIaalKMF-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819130027901.png)]

【JAVA中的有序表】：

TreeSet< ？> treeSet = new TreeSet<>();        //红黑树；

//只有一个KEY就是Set结构 ～

【K、V都有】：

TreeMap<Integer, String> treeMap1 = new TreeMap<>();

//所有的KEY之间有一种方式组织起来，而且是有序的。

【TreeMap常用API】：

【firstKey】：

加入的Key中最小的；

【lastKey】：

加入的Key中最大的；

【 floorKey(N) 】：

<=N , 并且离N最近的KEY是谁；

【 ceilingKey(N) 】：

>=N  , 并且离N最近的KEY是谁；

• 上述这些API，均是哈希表所没有的功能。

【性能上】：

TreeMap要比HashMap差一些，哈希表不论什么数据量 ， 增删改查都是常数级别的 ， 但是有序表，CRUD，你看到的所有的这些操作，时间复杂度是 O（logN） 级别的。

【有序表非基础类型】：

放入有序表的东西 ， 若不是基础类型，则必须提供比较器，自己定义的类型 ， 不告诉它比较规则，它是不知道应当如何进行比较的。

【有序表的固定操作】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2X25j5Pk-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819153031624.png)]

//大量的刷题过程中，你是不用知道它的原理的；

• 中等难度的题，都不会涉及到内部原理～

【5】：链表

【链表结构】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J1BvYWE8-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819153456559.png)]

【反转链表】：

反转单向链表，反转双向链表——水题；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-487RLMHf-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819153659280.png)]

【 链表函数的返回值 】：

• 链表的调整可能会存在“换头”的操作

函数就必须要带上返回值～～～！！！

函数在设计的时候——就应当带有Node类型的返回值～～～！！！

• 链表的调整不牵扯到换头的操作

返回值可以定义成 Void 类型 ～～～！！！

【图解】：

• 《@@43_8》

【6】：链表题目

【其他题目】：

除了我在课上讲的这些链表题目，之外的题目全部都是Coding问题～～～没有什么算法相关的东西；

【打印两个有序链表的公共部分】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mmvgjx4k-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819162517999.png)]

• 《@@43_9》

【链表面试方法论】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rIgpdZJ8-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819164305743.png)]

单链表和双链表的题目 ， 笔试和面试的要求是截然不同的；

【笔试】：

一律为了尽快通过，不要去纠结空间如何尽量省的方式来实现你的算法；

时间复杂度尽量低就行了；不要求空间复杂度的话，往往都很容易实现。

【面试】：

时间复杂度还是要求做到指标最优，但是此时一定要找到空间最省的方法。——其实就是在考Coding ， 此时如果不考虑空间的话，是无法给面试官留下深刻印象的；

【判断回文结构】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3fjm59x2-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819164705753.png)]

【理解链表的回文结构】：

• 《@@44_10》

//附带两种解题思路～

【如何得知指针是否进入了右侧区域呢？】：

//这就牵扯到了一个重要的概念——快慢指针。

//链表无法提前得知所有的数据状况，只能一个节点，一个节点地往下走。

【快慢指针】：

快指针一次走2步，慢指针一次走1步；

当快指针走完的时候，慢指针会来到中点的位置；

这个时候我便可以将慢指针后面的东西放到栈中去。

【实际需求各种各样】：

• 奇：

中点下一个；

• 偶

中点前一个的再前一个位置；

• 慢指针需要多/少 走个几步即可完成这种定制。

【三分链表】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eCGG9yoe-1663993781846)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819180957417.png)]

• 《@@_11》

【是能够达到稳定性的】：

数组中的parition是没有稳定性的，但是单链表是可以的。单链表移动没数组那么重，数组中间某个数插进去的话，后面所有的数都是要移动的。——单链表没这个问题。

[ 注意 ]:

三个区域中 ， 某一些区域实际可能并不存在～

最后在三块重连的时候，一定要讨论清楚边界～～～！！！

【 随机指针节点的链表 】：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0YKBpWgX-1663993781847)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819215352409.png)]

• rand指针可能指向其它节点、自己、null .