数据结构第十二周笔记—— 综合习题选讲1 (慕课浙大版本--XiaoYu)

习题选讲 - Insert or Merge

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

题意理解

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

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

捏软柿子算法

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

判断是否插入排序

1. 从左向右扫描，直到发现顺序不对，跳出循环
   
2. 从跳出地点继续向右扫描，与原始序列比对，发现不同则判断为"非"(如果是插入排序的话，所有的元素都是跟原始序列一模一样的)
   如果在对比的过程中发现不同，则跳出循环
   
3. 循环自然结束，则判断为"是"，返回跳出地点

1. 解析：(我们可以返回一个布尔值，例如非为0、是为1，但如果我返回的是"是"的话，插入排序要往下进行一步，简单返回一个1在我进行插入排序下一步的时候，还得从左向右扫描去找那个要执行下一步的那个点。所以我们返回"是"的)同时返回一个跳出的地点
   

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

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

判断归并段的长度

错误的想法：

1. 从头开始连续有序的子列长度？
   网络异常，图片无法展示

   |
   
   
2. 所有连续有序子列的最短长度？
   网络异常，图片无法展示

   |

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

for (l=2;l<=N;l*=2)

   //在保证了l是4的情况下，要检查看能不能是8，我们要重复前面的步骤看两段之间的衔接点是不是有序

1. 网络异常，图片无法展示

   |
   
   红色位置没有序了跳出循环(此时l为4，我们直接以4为归并段继续执行下一趟的归并就可以了)
   
   网络异常，图片无法展示

   |

其他数据测试

最小N(应该是多大？)

ps：边界测试是每道题里面测试非常重要的一个组成部分

N会是1吗？N等于1会出现什么情形？

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

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

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

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

最大N

习题选讲 - Sort with Swap(0,*)

习题-SWS.1 环的分类

题意理解

1. 给定N个数字的排列，如何仅利用与0交换达到排序目的？
   0在里面扮演了空位的问题
   
   网络异常，图片无法展示

   |
   
   

环的分类

网络异常，图片无法展示

|

习题-SWS.2 算法示例

对于不包含0的swap操作次数为n+1，包含0则是n-1次

习题选讲 - Hashing - Hard Version

习题-HHV 算法思路概述

这是哈希问题的逆问题

题意理解

1. 已知H(x) = x%N以及用线性探测解决冲突问题，模大小取决于目的有多少个下标
   
2. 先给出散列映射的结果，反求输入顺序

1. 当元素x被映射到H(x)位置，发现这个位置已经有y了，则y一定是在x之前被输入的
   

样例

限制：为了保证解是唯一的，当有几个元素都有可能是同时被插入的时候，我们是从小到大去插入的

因为12模11，余数为1，所以跟12冲突，放在12下面。后面都是类型的操作

依次输入顺序为