插入排序算法运行时间分析：最佳、最差和平均情况

插入排序是一种简单直观的排序算法，其时间复杂度取决于输入数据的排列情况。本文通过实验分析插入排序算法在不同输入数据情况下的运行时间变化，包括最佳情况（已排序）、最差情况（逆序）和平均情况。

1. 在不同的输入数据情况下，算法运行时间的变化

最佳情况： 当输入数据已经有序时，插入排序算法的运行时间最短，时间复杂度为 O(n)。
最差情况： 当输入数据是逆序的时候，插入排序算法的运行时间最长，时间复杂度为 O(n^2)。
平均情况： 插入排序算法的平均运行时间也为 O(n^2)，但比最差情况要好一些。

2. 不同情况下运行时间的初步分析

最佳情况下， 插入排序算法只需比较每个元素与其前一个元素的大小关系，不需要进行元素的移动操作，因此运行时间较短。
最差情况下， 插入排序算法需要将每个元素与已排序的部分进行比较，并进行多次的元素移动操作，导致运行时间较长。
平均情况下， 插入排序算法的运行时间介于最佳情况和最差情况之间，取决于输入数据的分布情况。

实验内容与步骤

整数的插入排序： 首先创建 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

def generate_random_numbers(size, range_start, range_end):
    return [random.randint(range_start, range_end) for _ in range(size)]

def generate_sorted_numbers(size, range_start, range_end):
    return [i for i in range(range_start, range_end + 1)]

def generate_reversed_numbers(size, range_start, range_end):
    return [i for i in range(range_end, range_start - 1, -1)]

def measure_time(arr):
    start_time = time.time()
    insertion_sort(arr)
    end_time = time.time()
    return end_time - start_time

def plot_histogram(times, title):
    plt.hist(times, bins=30, edgecolor='black')
    plt.axvline(np.mean(times), color='red', linestyle='dashed', linewidth=1)
    plt.axvline(np.min(times), color='green', linestyle='dashed', linewidth=1)
    plt.axvline(np.max(times), color='blue', linestyle='dashed', linewidth=1)
    plt.title(title)
    plt.xlabel('Time')
    plt.ylabel('Frequency')
    plt.show()

def plot_density(times, title):
    plt.hist(times, bins=30, density=True, edgecolor='black')
    plt.plot(np.linspace(np.min(times), np.max(times), 100), 
             np.exp(-0.5 * ((np.linspace(np.min(times), np.max(times), 100) - np.mean(times)) / np.std(times)) ** 2) / 
             (np.std(times) * np.sqrt(2 * np.pi)), color='red')
    plt.axvline(np.min(times), color='green', linestyle='dashed', linewidth=1)
    plt.axvline(np.max(times), color='blue', linestyle='dashed', linewidth=1)
    plt.title(title)
    plt.xlabel('Time')
    plt.ylabel('Density')
    plt.show()

def main():
    input_size = 1000000
    num_experiments = 998

    random_times = []
    sorted_times = []
    reversed_times = []

    for _ in range(num_experiments):
        random_numbers = generate_random_numbers(input_size, 0, input_size)
        random_times.append(measure_time(random_numbers))

    sorted_numbers = generate_sorted_numbers(input_size, 0, input_size)
    sorted_times.append(measure_time(sorted_numbers))

    reversed_numbers = generate_reversed_numbers(input_size, 0, input_size)
    reversed_times.append(measure_time(reversed_numbers))

    plot_histogram(random_times, 'Random Numbers')
    plot_histogram(sorted_times, 'Sorted Numbers')
    plot_histogram(reversed_times, 'Reversed Numbers')

    plot_density(random_times, 'Random Numbers')
    plot_density(sorted_times, 'Sorted Numbers')
    plot_density(reversed_times, 'Reversed Numbers')

    print("Random Numbers - Mean:", np.mean(random_times), "Standard Deviation:", np.std(random_times))
    print("Sorted Numbers - Mean:", np.mean(sorted_times), "Standard Deviation:", np.std(sorted_times))
    print("Reversed Numbers - Mean:", np.mean(reversed_times), "Standard Deviation:", np.std(reversed_times))

if __name__ == '__main__':
    main()

这段代码会生成随机整数、已排序整数和逆序整数，并对它们进行插入排序，并记录运行时间。然后使用 matplotlib 库绘制直方图和概率密度图，并计算平均值和标准差。最后打印出结果。