用函数模版写出插入排序算法c++

以下是使用函数模板写出插入排序算法的C++代码：

template <typename T>
void insertionSort(vector<T>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        T key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

该算法使用了模板，可以对任何类型的数组进行排序。在排序过程中，将数组分为已排序和未排序两部分，每次从未排序部分中取出一个元素，插入到已排序部分中的正确位置。时间复杂度为O(n^2)。