算法运行时间分析实验：最佳情况、最坏情况和平均情况

实验2 最佳情况、最坏情况和平均情况下算法运行时间的分析

实验地点: 实验日期: 成绩:

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

实验目的:

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

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

实验内容与步骤:

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

实验结果分析:

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