用函数模版写出插入排序算法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)。

相关问题

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

C++:随机函数产生10000个随机数，用起泡排序、归并排序、选择排序、插入排序等排序方法排序，并统计每一种排序所花费的时间。要求写出完整代码，并在软件Visual Studio 2022上成功运行出结果

在C++中，首先我们需要包含`<random>`库来生成随机数，然后使用`chrono`库来测量时间。以下是使用四种基本排序算法对10000个随机整数进行排序并计算时间的示例代码。请注意，为了在Visual Studio 2022上运行此代码，你需要创建一个控制台应用程序项目。

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

// 定义排序函数模板
template <typename T>
void sortFunction(std::vector<T>& arr, const std::string& name) {
    auto start = std::chrono::high_resolution_clock::now();

    // 使用指定的排序算法
    if (name == "Bubble Sort") {
        bubbleSort(arr);
    } else if (name == "Merge Sort") {
        mergeSort(arr);
    } else if (name == "Selection Sort") {
        selectionSort(arr);
    } else if (name == "Insertion Sort") {
        insertionSort(arr);
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "Time taken for " << name << ": " << duration.count() << " microseconds\n";
}

// 各种排序算法实现
void bubbleSort(std::vector<int>& arr) {
    // ... 写入冒泡排序的具体实现
}

void mergeSort(std::vector<int>& arr) {
    // ... 写入归并排序的具体实现
}

void selectionSort(std::vector<int>& arr) {
    // ... 写入选择排序的具体实现
}

void insertionSort(std::vector<int>& arr) {
    // ... 写入插入排序的具体实现
}

int main() {
    int size = 10000;
    std::vector<int> randomNumbers(size);

    // 生成随机数
    std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> distribution(0, 9999); // 或者根据需要调整范围
    for (auto& num : randomNumbers)
        num = distribution(generator);

    // 对每个排序算法排序并计时
    sortFunction(randomNumbers, "Bubble Sort");
    sortFunction(randomNumbers, "Merge Sort");
    sortFunction(randomNumbers, "Selection Sort");
    sortFunction(randomNumbers, "Insertion Sort");

    return 0;
}

在这个代码中，你需要填写各个排序算法的具体实现。为了在Visual Studio 2022上运行，将上述代码复制到一个新的`.cpp`文件中，创建一个新的控制台应用程序项目，添加该文件并在项目构建时编译运行。