使用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;

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

在这个例子中，`T`是一个模板参数，代表任何类型的数据。`arr[]`是输入数组，`n`是数组的长度。函数通过遍历数组，将每个元素与前面的元素比较并交换，直到找到合适的位置将当前元素插入已排序的部分。

相关问题

使用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`函数模板接受一个任意类型的数据数组和它的大小作为参数。通过这种方式，你可以对整数数组、浮点数数组甚至是自定义类型的数据进行插入排序。

使用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;
}