习题选讲 Insert or Merge

2020-03-16 73浏览

  • 1.第十二讲 习题选讲 浙江大学 陈 越
  • 2.09-2. Insert or Merge
  • 3.题意理解  如何区分简单插入和非递归的归并排序 SampleInput:10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0 10 3 1 2 8 7 5 9 4 0 6 1 3 2 8 5 7 4 9 0 6  插入排序：前面有序，后 面没变化  归并排序：分段有序
  • 4.捏软柿子算法  判断是否插入排序     从左向右扫描，直到发现顺序不对，跳出循环 从跳出地点继续向右扫描，与原始序列比对，发现 不同则判断为“非” 循环自然结束，则判断为“是”，返回跳出地点 如果是插入排序，则从跳出地点开始进行一趟 插入
  • 5.判断归并段的长度  从头开始连续有序的子列长度？ 2 1 8 9 6 5 3 4 1 2 8 9 5 6 3 4  所有连续有序子列的最短长度？ 4 2 1 3 13 14 12 11 8 9 7 6 10 5 1 2 3 4 11 12 13 14 6 7 8 9 5 10  for ( l=2; l<=N; l*=2 )
  • 6.其它测试数据  最小N（应该是多大？）  插入排序第1步，什么都没改变  归并排序第1步，什么都变了  尾部子列无变化，但是前面变了（归并）  最大N