题目1：给定n个数值，从小到大排序。 要求： 1. 输入随机生成0≦x≦10^9数组，长度分别为5、10、100； 2. 采用插入排序输出每次执行的排序结果 3. 时间复杂度、空间复杂度、实际执行时间、实际占用内存空间？ 给出c++代码

题目1描述的是要求对一组整数数组进行排序，并使用插入排序算法来完成任务。插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

以下是C++代码示例：

#include <iostream>
#include <vector>
#include <ctime>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    // 生成随机数组
    srand(time(0));
    std::vector<int> testArrays[] = {std::vector<int>(5, 0), std::vector<int>(10, 0), std::vector<int>(100, 0)};
    for (size_t i = 0; i < sizeof(testArrays) / sizeof(testArrays[0]); ++i) {
        for (auto& num : testArrays[i]) {
            num = rand() % 100000000;  // 生成0到1亿之间的随机数
        }

        // 插入排序并打印结果
        insertionSort(testArrays[i]);
        std::cout << "Sorted array of length " << testArrays[i].size() << ": ";
        for (const auto& val : testArrays[i]) {
            std::cout << val << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

**分析：**

- **时间复杂度**：插入排序的时间复杂度在最坏的情况下（输入逆序）是O(n^2)，但在最好情况下（已经排序）是O(n)。平均情况下也是O(n^2)。
- **空间复杂度**：插入排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。
- **实际执行时间和内存空间**：这些会依赖于特定计算机硬件和编译器优化程度。上面的代码在处理不同规模的数组时会有差异，小规模的数组更快，大规模数组则可能需要更多时间。