请在顺序表结构上编写冒泡排序算法，要求递归和非递归两种方法。使用c或者c++

在顺序表结构上，我们可以使用两种方法实现冒泡排序：递归法和非递归法。

**非递归方法（迭代）**

#include <iostream>
using namespace std;

// 冒泡排序函数，用于升序排列
void bubbleSort(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;
            }
        }
    }
}

// 测试函数
void testBubbleSort(int arr[], int size) {
    cout << "Original array: ";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    bubbleSort(arr, size);
    cout << "\nSorted array: ";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    testBubbleSort(arr, n);
    return 0;
}

**递归方法**

由于冒泡排序不适合直接用递归实现（因为每一轮都会缩小未排序区间，直到只剩一个元素），通常我们会采用一种“模拟”递归的方式，通过嵌套循环来达到同样的效果。但是为了清晰起见，这里展示的是一个简单的例子，它实际上不是真正的递归，而是伪递归：

#include <iostream>
using namespace std;

// 这里的bubbleSortRecursion是一个辅助函数，主要用于演示递归思想
void bubbleSortRecursion(int arr[], int start, int end) {
    if (start >= end)
        return;

    for (int i = start; i < end; i++) {
        if (arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i + 1]); // 交换元素
        }
    }

    // 递归处理剩余部分
    bubbleSortRecursion(arr, start + 1, end);
}

// 测试函数同上
void testBubbleSortRecursion(int arr[], int size) {
    bubbleSortRecursion(arr, 0, size - 1);
    // 实际上不需要显式返回，因为主函数会自动结束
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    testBubbleSortRecursion(arr, n);
    return 0;
}