实验二：插入排序算法运行时间分析（最佳、最坏和平均情况）

实验二：插入排序算法运行时间分析（最佳、最坏和平均情况）

实验地点：

实验日期：

成绩：

实验设备/软件/平台等：

实验目的：

1. 探究插入排序算法的运行时间在不同输入数据情况下的变化。
2. 对不同情况下的运行时间进行初步分析。

**实验原理：**排序算法（插入排序）

实验内容与步骤：

1. **对整数进行插入排序：**创建n个随机整数并对其进行排序。请确保排序程序能够正确运行。
2. **输入大小为1000000，创建998组随机整数，数据范围在0到1000000或更大之间。**记录这998组整数的运行时间。
3. 创建一组已排序的整数（输入大小和范围相同），并记录运行时间。
4. 创建一组逆序排列的整数（输入大小和范围相同），并记录运行时间。

实验结果分析：

1. 根据这1000次运行时间绘制直方图，并在上面标记出最佳情况和最坏情况。
2. 绘制这1000次运行时间的概率密度直方图和曲线，并在上面标记出最佳情况和最坏情况。
3. 计算这1000次运行时间的平均值和标准差。
4. 根据图表讨论对插入排序算法运行时间的深入认识。