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

题目1要求我们对随机生成的整数数组进行从小到大的排序，使用快速排序算法。以下是使用C++实现的快速排序示例：

#include <iostream>
#include <vector>
#include <cstdlib> // 用于rand()函数
#include <ctime>   // 用于srand(time(NULL))

// 交换两个元素的位置
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 快速排序函数
template<typename T>
void quickSort(T arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 计算并返回分区索引
int partition(T arr[], int low, int high) {
    T pivotValue = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 指针i初始化为低值

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivotValue) {
            i++; // 如果当前元素小于基准，移动指针i并将两者交换
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准放到正确位置
    return i + 1;
}

// 主函数
int main() {
    srand(time(0)); // 设置随机数种子
    int n;
    std::cout << "Enter the length of array (5, 10, or 100): ";
    std::cin >> n;

    switch (n) {
        case 5:
            std::vector<int> shortArray(5, 0); // 创建大小为5的随机数组
            for (int i = 0; i < 5; i++) {
                shortArray[i] = rand() % 1000; // 生成0-999之间的随机数
            }
            std::cout << "Sorting 5 elements...\n";
            quickSort(shortArray.data(), 0, shortArray.size() - 1);
            break;
        case 10:
            std::vector<int> mediumArray(10, 0);
            for (int i = 0; i < 10; i++) {
                mediumArray[i] = rand() % 1000;
            }
            std::cout << "Sorting 10 elements...\n";
            quickSort(mediumArray.data(), 0, mediumArray.size() - 1);
            break;
        case 100:
            std::vector<int> longArray(100, 0);
            for (int i = 0; i < 100; i++) {
                longArray[i] = rand() % 1000;
            }
            std::cout << "Sorting 100 elements...\n";
            quickSort(longArray.data(), 0, longArray.size() - 1);
            break;
        default:
            std::cerr << "Invalid length! Exiting.\n";
            return 1;
    }

    // 输出排序后的数组
    std::cout << "Sorted Array:\n";
    for (const auto& num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

**性能分析：**

- 时间复杂度：平均情况下的时间复杂度是O(n log n)，最坏情况（数组完全逆序）下是O(n^2)，但在实践中快速排序通常是高效的。
- 空间复杂度：由于递归调用栈，空间复杂度为O(log n)的额外空间，因为需要保存每个递归调用的信息。

**实际执行时间和内存占用：**

这将取决于具体的硬件环境，上述代码仅给出了基本的逻辑，实际运行时会有所不同。为了得到准确的时间和内存消耗，你需要在特定环境下用编译器（如g++）运行程序，并使用性能分析工具进行测量。例如，可以使用`chrono`库来测量执行时间，而内存使用则可以使用操作系统提供的命令行工具（如Linux上的`time`或Windows上的`Task Manager`）。