乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
题设给定两组数, 第二组数是第一组数用插入排序或归并排序进行排序的某个中间状态,
要求判断使用的是哪种排序, 并用这种排序算法对排序的中间状态再排序一次并输出.
从题设中我们识别到两个功能需求:
- 判断所使用的排序算法
- 使用对应排序算法再进行一次排序
根据插入排序的特征, 排序过程中数组左半部分为排序部分, 右半部分为未排序部分.
而归并排序会同时变动整个数组.
题设保证了每组测试结果唯一, 所以不用担心出现插入排序和归并排序中间状态一致的情况.
我们只需要检查排序中间状态的数组是否符合"左边最长有序部分之外的另一部分是否是未排序部分(即与原数组对应部分完全西昂同)"
即, 检查第二个序列升序部分的末尾索引, 然后从该位置开始检查直到数组末尾是否都和原数组一致
插入排序第n次的结果和第n+1次的结果, 差别在于: 左边有序部分的长度.
所以我们只需要对左起的n个元素进行排序, 其余部分不变, 排序的结果就是插入排序n次后的结果.
归并排序第n次的结果和第n+1次的结果, 差别在于: 有序区块的长度.
比如对于数列 [3, 1, 2, 8, 7, 5, 9, 4, 6, 0]
第1次