c＋＋数据结构与算法问题

Question

实验任务:分别用迭代算法、递归算法实现整数的冒泡排序。
实验步骤: 使用经典冒泡排序算法实现对个数不确定的整数元素进行排序，整数元素可分为以下两种情况：数据元素大小随机排列；数据元素为逆序排列。整数个数长度为1000,10000，分别比较以上不同数据元素分布情况下不同长度整数元素排序的运算时间。提示：c++的头文件ctime/time.h中的库函数clock()提供了测试函数运行时间的方法。

实验结果:1、给出不同情况下冒泡算法消耗的运算时间情况截图。2、试将获得的实验结果与冒泡排序算法的理论时间复杂度进行比

Answer 1

参考gpt
以下是用迭代算法和递归算法实现整数的冒泡排序的示例代码：

迭代算法实现冒泡排序：

#include <iostream>
#include <ctime>

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

int main() {
    const int size = 1000;
    int arr[size];

    // 初始化数组，可以根据需要进行修改

    // 计算运行时间
    clock_t start = clock();
    bubbleSort(arr, size);
    clock_t end = clock();

    // 输出运行时间
    double timeTaken = double(end - start) / CLOCKS_PER_SEC;
    std::cout << "运行时间：" << timeTaken << "秒" << std::endl;

    return 0;
}

递归算法实现冒泡排序：

#include <iostream>
#include <ctime>

void bubbleSortRecursive(int arr[], int n) {
    if (n == 1)
        return;

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

    bubbleSortRecursive(arr, n-1);
}

int main() {
    const int size = 1000;
    int arr[size];

    // 初始化数组，可以根据需要进行修改

    // 计算运行时间
    clock_t start = clock();
    bubbleSortRecursive(arr, size);
    clock_t end = clock();

    // 输出运行时间
    double timeTaken = double(end - start) / CLOCKS_PER_SEC;
    std::cout << "运行时间：" << timeTaken << "秒" << std::endl;

    return 0;
}