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

在C++中，模板函数是一种强大的工具，可以创建通用算法，适用于不同类型的数据。让我们首先了解如何使用模板实现插入排序算法，并添加一个降序版本。

插入排序的基本思想是将元素逐个插入到已排序的部分，直到整个序列有序。下面是普通插入排序的C++模板函数示例：

template <typename T>
void insertionSort(T arr[], int n) {
    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;
    }
}

在这个例子中，`T`是一个类型参数，代表任意类型，如`int`, `double`, `string`等。我们对数组`arr`进行操作，如果`arr[j]`大于`key`(当前待插入的元素)，就将`arr[j]`向右移动一位。

为了实现降序排序，只需稍微修改比较条件即可，如下：

template <typename T>
void descendingInsertionSort(T arr[], int n) {
    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;
    }
}

现在，你可以使用这两种函数对各种类型的数组进行升序和降序排序：

int main() {
    int numbers[] = {5, 2, 9, 1, 7};
    double doubles[] = {4.8, 1.3, 6.7, 2.1, 8.5};

    insertionSort(numbers, sizeof(numbers) / sizeof(numbers[0]));
    descendingInsertionSort(doubles, sizeof(doubles) / sizeof(doubles[0]));

    std::cout << "Sorted integers in ascending order: ";
    for (const auto& num : numbers)
        std::cout << num << " ";
    std::cout << "\nSorted doubles in descending order: ";
    for (const auto& num : doubles)
        std::cout << num << " ";

    return 0;
}