插入排序算法运行时间分析：不同输入数据下的性能表现

本实验旨在研究插入排序算法在不同输入数据情况下运行时间的变化，并通过可视化图表和统计指标分析其性能特点。

实验内容与步骤

整数的插入排序: 创建n个随机整数，并对其进行排序。确保排序程序运行正确。
输入大小=1000000: 创建998组随机整数，数据范围在0到1000000之间或更大。记录998组整数的运行时间。
创建一组已排序的整数: 创建一组已排序的整数，输入大小和范围与第二步相同。记录运行时间。
创建一组反排序的整数: 创建一组反排序的整数，输入大小和范围与第二步相同。记录运行时间。

实验结果分析

在1000次运行时间的基础上绘制一个直方图，并在上面标出最佳情况和最差情况。
画出1000次运行时间的概率密度直方图和曲线，并在其上标出最好和最坏的情况。
计算1000次运行的平均值和标准差。
根据图表讨论你对算法运行时间的更深入的了解。

Python代码进行可视化

import random
import time
import matplotlib.pyplot as plt
import numpy as np

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 生成n个随机整数
n = 1000000
arr = [random.randint(0, n) for _ in range(n)]

# 整数的插入排序
start_time = time.time()
insertion_sort(arr)
end_time = time.time()
execution_time = end_time - start_time
print('整数的插入排序运行时间：', execution_time)

# 输入大小为1000000的情况
num_of_tests = 998
execution_times = []

for _ in range(num_of_tests):
    arr = [random.randint(0, n) for _ in range(n)]
    start_time = time.time()
insertion_sort(arr)
end_time = time.time()
execution_time = end_time - start_time
execution_times.append(execution_time)

# 创建一组已排序的整数
arr = list(range(n))
start_time = time.time()
insertion_sort(arr)
end_time = time.time()
best_case_time = end_time - start_time

# 创建一组反排序的整数
arr = list(range(n, 0, -1))
start_time = time.time()
insertion_sort(arr)
end_time = time.time()
worst_case_time = end_time - start_time

# 绘制直方图
plt.hist(execution_times, bins=30, edgecolor='black')
plt.axvline(x=best_case_time, color='green', linestyle='dashed', linewidth=2, label='Best Case')
plt.axvline(x=worst_case_time, color='red', linestyle='dashed', linewidth=2, label='Worst Case')
plt.xlabel('Execution Time')
plt.ylabel('Frequency')
plt.legend()
plt.show()

# 绘制概率密度直方图和曲线
plt.hist(execution_times, bins=30, density=True, edgecolor='black')
plt.plot(np.linspace(0, max(execution_times), 100), [1 / max(execution_times)] * 100, 'g--', label='Best Case')
plt.plot(np.linspace(0, max(execution_times), 100), [1 / min(execution_times)] * 100, 'r--', label='Worst Case')
plt.xlabel('Execution Time')
plt.ylabel('Probability Density')
plt.legend()
plt.show()

# 计算平均值和标准差
average_time = np.mean(execution_times)
std_deviation = np.std(execution_times)
print('平均值：', average_time)
print('标准差：', std_deviation)

结论

通过实验结果分析，我们可以得出以下结论：

当输入数据已经有序时，插入排序的运行时间最短，因为不需要进行元素的移动操作。
当输入数据完全逆序时，插入排序的运行时间最长，因为每个元素都需要向前移动到正确的位置。
在随机数据情况下，插入排序的运行时间介于最佳情况和最差情况之间，其平均运行时间和标准差可以反映算法在一般情况下的性能表现。

讨论

本实验仅针对插入排序算法进行分析，其他排序算法可能会有不同的性能特点。此外，输入数据的大小和范围也会影响算法的运行时间。因此，在实际应用中需要根据具体情况选择合适的排序算法。