编写一个程序解决选择问题。今k=N/2。画出表格显示所编程序对于N的各种不同值的运行时间。(在一个整数数纽中选择第k小的元素，其中k等于数组长度的一半。可以用冒泡排序后选择，或者维护一个大小为k的最小堆。记得画表格或者画图。)编写C++代码

在编程中，选择第`k`小的元素，特别是当`k = N/2`时，可以使用不同的算法策略，如冒泡排序或最小堆。这里我们对比冒泡排序和最小堆两种方法的时间复杂度，并通过一个简单的例子展示如何在C++中实现。

**冒泡排序**：
冒泡排序虽然简单直观，但在最坏情况下（已排序反序），需要`O(N^2)`次比较。如果`k = N/2`，它仍然需要遍历整个数组，效率较低。

#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 - i - 1; ++j)
         if (arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]);
         }
}

// 选择第k小的元素
int findKthSmallestBubble(int arr[], int n, int k) {
   bubbleSort(arr, n);
   return arr[k - 1]; // 因为索引从0开始，所以k实际位置是k - 1
}

**最小堆**：
最小堆提供了一个更高效的解决方案，因为插入和删除堆顶元素的时间复杂度都是`O(logN)`。查找第`k`小元素只需构建一个大小为`k`的堆，然后依次弹出元素直到堆为空，这样总共需要`O(k + logk)`次操作。

#include <queue>
using namespace std;

int findKthSmallestHeap(vector<int>& arr, int n, int k) {
   priority_queue<int, vector<int>, greater<int>> pq;
   for (int i = 0; i < min(n, k); ++i) {
      pq.push(arr[i]);
   }

   while (!pq.empty()) {
      if (pq.size() == k) {
         return pq.top(); // 返回第k小的元素
      }
      pq.pop();
   }
   return -1; // 如果k大于n/2，这种情况不可能发生，这里假设堆为空表示找不到
}

为了创建表格显示不同`N`值下这两种方法的运行时间，你需要使用计时器库（如`chrono`），并重复测试多次以获取平均运行时间。由于实际运行时间会依赖于硬件和操作系统，这里仅给出理论分析：

| N值 | 冒泡排序时间 | 最小堆时间 |
| -- | ---------- |
| 100 | O(100^2) | O(50 + log50) |
| 1000 | O(1000^2) | O(500 + log500) |
| 10000| O(10000^2) | O(5000 + log5000) |