用c++求解把有20个整数元素的数组用选择排序法按由小到大升序排列。今再输入一个数，要求按原来排序的规律将它插入数组中

在C++中，我们可以使用选择排序算法来对一个包含20个整数的数组进行升序排列，然后再添加一个新的数并保持原有的顺序。以下是基本步骤：

1. **选择排序**:
- 首先，遍历整个数组。
- 对于每个索引i，找到剩余部分中的最小值的索引min_index。
- 将找到的最小值与当前位置i交换。
- 重复这个过程，直到数组完全排序。

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        // 交换arr[i]和arr[min_index]
        std::swap(arr[i], arr[min_index]);
    }
}

2. **插入新数**:
- 完成选择排序后，可以按照原排序数组的大小顺序遍历，直到找到第一个大于新数的位置，然后将新数插入。

// 假设新数为new_num
for (int i = 0; i < n && arr[i] <= new_num; i++) {}
arr[i] = new_num;

完成这两步后，数组就会按照原始排序的顺序，并在适当位置插入了新的数。

**相关问题**:
1. 选择排序的时间复杂度是多少？
2. 如果数组已经部分排序，选择排序是否还是最优选择？
3. 插入操作对于选择排序的整体效率有何影响？