使用C++ 模板函数，实现插入排序，并举例

在C++中，模板函数是一种强大的工具，它允许你编写一次通用的函数，可以处理任意类型的值，只要这些值支持基本的算术操作。下面是一个使用模板函数实现插入排序的例子：

#include <iostream>

// 定义一个模板函数，用于通用的比较操作
template <typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; ++i) {
        T key = arr[i];
        int j = i - 1;

        // 将大于key的元素逐步后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;  // 插入键值到正确位置
    }
}

// 测试函数，这里假设arr是一个整数数组
int main() {
    int numbers[] = {9, 5, 7, 1, 8, 6};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    std::cout << "Original array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }

    insertionSort(numbers, size);

    std::cout << "\nSorted array: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }

    return 0;
}

在这个例子中，`insertionSort`函数模板接受一个任意类型的数据数组和它的大小作为参数。通过这种方式，你可以对整数数组、浮点数数组甚至是自定义类型的数据进行插入排序。