数据结构面试常见问题之Insert or Merge

😀前言
本文将讨论如何区分插入排序和归并排序两种排序算法。我们将通过判断序列的有序性来确定使用哪种算法进行排序。具体而言，我们将介绍判断插入排序和归并排序的方法，并讨论最小和最大的能区分两种算法的序列长度。

🏠个人主页：尘觉主页

💕欢迎大家：这里是CSDN，我总结知识的地方，欢迎来到我的博客，感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教先在次感谢啦😊

文章目录

Insert or Merge
- 习题-IOM.1 插入排序的判断
- - 题意理解
  - 捏软柿子算法
- 习题-IOM.2 归并段的判断
- - 判断归并段的长度
- 其他数据测试
- 😄总结

Insert or Merge

习题-IOM.1 插入排序的判断

题意理解

如何区分简单插入和非递归的归并排序

插入排序：前面有序，后面没有变化
归并排序：分段有序

捏软柿子算法

ps：在插入和归并两种算法里，哪种算法比较容易判断？插入排序
判断是否插入排序

从左向右扫描，直到发现顺序不对，跳出循环
从跳出地点继续向右扫描，与原始序列比对，发现不同则判断为"非"(如果是插入排序的话，所有的元素都是跟原始序列一模一样的)
如果在对比的过程中发现不同，则跳出循环
循环自然结束，则判断为"是"，返回跳出地点
1. 解析：(我们可以返回一个布尔值，例如非为0、是为1，但如果我返回的是"是"的话，插入排序要往下进行一步，简单返回一个1在我进行插入排序下一步的时候，还得从左向右扫描去找那个要执行下一步的那个点。所以我们返回"是"的)同时返回一个跳出的地点

如果是插入排序，则从跳出地点开始进行一趟插入

习题-IOM.2 归并段的判断

判断归并段的长度

错误的想法：

从头开始连续有序的子列长度？
所有连续有序子列的最短长度？
1. 这个其实是四个一段的，但前8个刚好都是有序的
2. 保险正确的判断方法：从原始序列出发，真的在做归并排序，每归并一趟就把归并的中间结果跟这个结果的序列做一个比对。什么时候每一个数都对上了就再把当前的归并多执行一次然后
  输出结果

3.for (l=2;l<=N;l*=2)
//在保证了l是4的情况下，要检查看能不能是8，
//我们要重复前面的步骤看两段之间的衔接点是不是有序

在这里插入图片描述
红色位置没有序了跳出循环(此时l为4，我们直接以4为归并段继续执行下一趟的归并就可以了)

其他数据测试

最小N(应该是多大？)
ps：边界测试是每道题里面测试非常重要的一个组成部分
N会是1吗？N等于1会出现什么情形？

N等于1就意味着整个序列里面只有一个数字，在排序前它是一个数字，在排序之后他仍然是同一
个数字，在这种情况下我不管是使用插入排序还是归并排序得到的都会是同样的结果，这样解就不
是唯一的。我们题目输出的要求是插入排序或者归并排序的其中一个，所以N=1是绝对不可以的

保证可以区分两种算法的最小N应该是：4(区分插入排序与归并排序最小要求)

插入排序第一步，什么都没变
归并排序第一步，什么都变了

尾部子列无变化，但前面变了(归并)最大N

😄总结

通过本文的介绍，我们了解了如何判断插入排序和归并排序两种算法。对于插入排序，我们可以通过从左到右扫描序列并与原始序列进行比对，如果遇到不同的元素，则判断为归并排序；如果扫描结束后没有发现不同的元素，则判断为插入排序。而对于归并排序，我们可以通过多次归并并将归并的中间结果与原始序列进行比对，直到每个元素都匹配成功，即可判断为归并排序。

此外，我们还讨论了最小和最大能区分插入排序和归并排序的序列长度。最小长度为4，因为在长度为4的序列中，插入排序的第一步不会改变序列的顺序，而归并排序的第一步会改变序列的顺序。而最大长度没有明确的界限，因为归并排序可以应对任意长度的序列。

通过掌握这些判断方法和序列长度的特点面试就不用担心啦祝您成功

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC