2. 分别编写函数，用递归及非递归的方式实现冒泡排序算法；然后用一个整数序列测试递归及非递归方式下的执行效率。

好的，开始回答您的问题。

以下是递归方式实现冒泡排序的函数：

void recursiveBubbleSort(int arr[], int n){
  // Base case
  if(n == 1){
    return;
  }

  // One pass of bubble sort. After this pass, the largest element is moved (or bubbled) to end.
  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;
    }
  }

  // Recursively sort remaining array
  recursiveBubbleSort(arr, n - 1);
}

以下是非递归方式实现冒泡排序的函数：

void iterativeBubbleSort(int arr[], int n){
  for(int i = 0; i < n - 1; i++){
    // Last i elements are already in place
    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;
      }
    }
  }
}

接下来，使用一个整数序列测试递归及非递归方式下的执行效率，可以编写以下代码：

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

void recursiveBubbleSort(int arr[], int n){
  // Base case
  if(n == 1){
    return;
  }

  // One pass of bubble sort. After this pass, the largest element is moved (or bubbled) to end.
  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;
    }
  }

  // Recursively sort remaining array
  recursiveBubbleSort(arr, n - 1);
}

void iterativeBubbleSort(int arr[], int n){
  for(int i = 0; i < n - 1; i++){
    // Last i elements are already in place
    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 = 10000;

  int arr[SIZE];
  for(int i = 0; i < SIZE; i++){
    arr[i] = rand() % 1000;
  }

  // Measure time taken for recursive bubble sort
  auto start1 = high_resolution_clock::now();
  recursiveBubbleSort(arr, SIZE);
  auto end1 = high_resolution_clock::now();
  auto duration1 = duration_cast<microseconds>(end1 - start1);
  cout << "Time taken for recursive bubble sort: " << duration1.count() << " microseconds" << endl;

  // Measure time taken for iterative bubble sort
  auto start2 = high_resolution_clock::now();
  iterativeBubbleSort(arr, SIZE);
  auto end2 = high_resolution_clock::now();
  auto duration2 = duration_cast<microseconds>(end2 - start2);
  cout << "Time taken for iterative bubble sort: " << duration2.count() << " microseconds" << endl;

  return 0;
}

这个程序会生成一个大小为10000的随机整数序列，并且打印出递归及非递归方式下的执行时间。运行多次，可以对两种排序算法的效率进行比较。