用c++编写使用插入排序法进行排序的算法，并给出最好情况、最坏情况、 平均情况下的时间复杂度。

在C++中，我们可以使用插入排序法来对一组数据进行排序。插入排序的基本思想是将每个元素依次插入到已排序的部分中找到其正确的位置。以下是简单的插入排序算法示例：

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将key之前的所有元素向右移动，直到找到合适位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入关键值
    }
}

// 测试代码
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    return 0;
}

**时间复杂度分析：**

- **最好情况（已经排序的数组）**：插入排序在数组已经排序的情况下，每次只需要比较当前元素与已排序部分的最后一个元素即可，因此最好的时间复杂度是O(n)，这里n是数组长度。

- **最坏情况（逆序数组）**：当数组完全逆序时，每一步都需要比较并移动所有之前元素才能找到正确位置，所以最坏的时间复杂度是O(n^2)。

- **平均情况**：由于插入排序在中间状态可能会反复交换元素，平均下来它的性能介于最好和最坏之间，也是O(n^2)。