Lab 2

教学团队

教师：郑骁庆

联系方式：zhengxq@fudan.edu.cn

助教：

• 陈雷远 20210240034@fudan.edu.cn
• 徐健涵 20210240021@fudan.edu.cn

任务

• 归并排序

• 插入排序

• 归并插入优化排序

本节目标：

1. 掌握归并排序与插入排序的算法
2. 掌握指定排序的复杂度
3. 对归并排序与插入排序有一定自己的思考

获取及提交lab

获取：通过 https://github.com/2020-Data-structure-and-algorithm/lab2，获取。

提交：将提交物放到自己lab2的文件夹中，将文件夹压缩，压缩文件名应为你的 学号_姓名 （如20210240034_陈雷远），提交至 FTP 站点（ftp://10.12.5.33）本课程文件夹的work_upload/lab2 文件夹下。

提交物：本课程要求使用java或python语言完成，本次lab如果用java语言完成需提交InsertionSort.java, MergeSort.java 以及 OptSort.java；python语言需提交InsertionSort.py, MergeSort.py 以及 OptSort.py。本次实验需要提交说明文档，请大家注意。

截止时间：2020年9月30日 23：59：59

1.设计归并排序

问题描述

设计一个归并排序，要求输入为数组形式，输出为数组形式。

示例：

输入：
[4 ,5 ,7 ,8 ,1, 2, 6, 3]

输出：
[1, 2, 3, 4, 5, 6, 7 ,8]

2.设计插入排序

问题描述

设计一个插入排序，要求输入为数组形式，输出为数组形式。

###示例：

同上：
输入：
[4 ,5 ,7 ,8 ,1, 2, 6, 3]

输出：
[1, 2, 3, 4, 5, 6, 7 ,8]

3.设计优化排序

问题描述

需要先进行第三问的解答，在文档中写出自己对复杂度的想法与理由以及复杂度式子

归并排序的效率可以通过插入排序进行改善，具体可以通过限制长度的形式来做到，可以通过计时器计时 进行实验。将自己的实验结果用文档的形式记录下来，并在OptSort.__文件中保留实验中最好的结果即可。