4. 插入排序问题（必做） （1） 编写插入排序程序。要求将插入排序写成函数。 （2）生成长度为N的伪随机序列，对伪随机序列进行插入排序。N=10000,30000,50000 （3）并计算排序耗费的时间。 python

插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

以下是Python中插入排序的基本实现，作为一个函数：

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
    return arr

为了完成题目中的任务，你需要首先生成长度分别为10000、30000和50000的随机数列表，然后分别对其进行插入排序，并测量每个步骤所需的时间。你可以使用Python的`time`模块来获取时间：

import time

# 预设长度
N_values = [10000, 30000, 50000]

for N in N_values:
    # 生成随机数列表
    random_list = [random.randint(0, 1000) for _ in range(N)]
    
    # 开始计时
    start_time = time.time()
    
    sorted_list = insertion_sort(random_list)
    
    # 结束计时
    end_time = time.time()
    
    # 计算排序时间
    sort_time = end_time - start_time
    print(f"对于长度为{N}的列表，插入排序耗时: {sort_time}秒")

记得安装`random`模块，如果还没有的话，可以添加 `import random` 在代码开始处。