请编写复杂度为O(n 2 )、O(nlogn)、O(n)的任意程序，在不同问题规模下，记录运行时间，注明单位秒s或毫秒ms，对于运行时间过长的，给出预估时间。 鼓励使用C语言做比较。注意：编译时请不要用代码优化参数。

为了演示复杂度分别为 O(n^2)，O(nlogn) 和 O(n) 的算法，我们分别选择冒泡排序、快速排序和线性搜索。以下是C语言的简单示例：

1. O(n^2) 冒泡排序 (最差情况下的时间复杂度):

#include <stdio.h>
#include <time.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 记录开始时间和结束时间
double measure_time() {
    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);
    // ... 程序执行代码
    clock_gettime(CLOCK_MONOTONIC, &end);
    double diff = (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec);
    return diff / 1e6; // 转换为毫秒
}

int main() {
    int n = 100000; // 可调整规模
    int arr[n];

    // 生成随机数组
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        arr[i] = rand() % n;

    // 测试并记录时间
    double time_taken = measure_time();
    printf("Bubble sort for %d elements took %.2f ms\n", n, time_taken);

    return 0;
}

这个例子中，如果 `n` 很大，如百万级别，冒泡排序的时间会显著增加，可能会达到几分钟甚至几十分钟。

2. O(nlogn) 快速排序:

#include <stdio.h>
#include <time.h>

void quick_sort(int arr[], int low, int high) {
    // ... 快速排序实现省略
}

double quick_sort_measure_time() {
    // ... 时间测量逻辑与上面一样
}

int main() {
    int n = 1000000; // 更大的规模
    int arr[n];

    // ... 初始化和排序

    double time_taken = quick_sort_measure_time();
    printf("Quick sort for %d elements took %.2f ms\n", n, time_taken);

    return 0;
}

对于大规模数据，快速排序的时间大约在几秒钟到几十秒钟之间。

3. O(n) 线性搜索:

#include <stdio.h>
#include <time.h>

int linear_search(int arr[], int key, int n) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

double linear_search_measure_time() {
    // ... 时间测量逻辑与前面一样
}

int main() {
    int n = 1000000; // 同样巨大的规模
    int arr[n];
    int target;

    // ... 初始化和搜索

    double time_taken = linear_search_measure_time();
    printf("Linear search for an element in %d elements took %.2f ms\n", n, time_taken);

    return 0;
}

对于线性搜索，即使在非常大的数组上，由于其基本的遍历性质，它通常能在毫秒级别内完成。