插入排序算法实例代码

插入排序是一种简单直观的排序算法，具体思路是将一个元素插入到已排序好的数组中。其实现过程如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

以下是插入排序的示例代码（C++）：

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /*将比key大的元素往后移动*/
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

相关问题

写python插入排序算法并实例化

好的，下面是Python插入排序算法的代码：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

然后实例化一个数组并对其进行排序，示例代码如下：

arr = [9, 5, 1, 4, 3]
print("原始数组：", arr)
sorted_arr = insertion_sort(arr)
print("排序后的数组：", sorted_arr)

输出结果应该是：

原始数组： [9, 5, 1, 4, 3]
排序后的数组： [1, 3, 4, 5, 9]

插入排序C++份文件编写使用模板 注释

当我们需要在多个文件中编写使用模板的插入排序算法时，可以将算法的实现放在一个单独的源文件中，并将算法的声明放在头文件中。下面是一个示例：

**insertion_sort.h**（头文件）：

#ifndef INSERTION_SORT_H
#define INSERTION_SORT_H

#include <vector>

template <typename T>
void insertionSort(std::vector<T>& nums);

#endif

**insertion_sort.cpp**（源文件）：

#include "insertion_sort.h"

template <typename T>
void insertionSort(std::vector<T>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        T key = nums[i];
        int j = i - 1;

        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }

        nums[j + 1] = key;
    }
}

// 显式实例化
template void insertionSort<int>(std::vector<int>& nums);
template void insertionSort<float>(std::vector<float>& nums);
// 可以根据需要继续添加其他类型的实例化

**main.cpp**（主程序文件）：

#include <iostream>
#include <vector>
#include "insertion_sort.h"

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 3};

    std::cout << "排序前：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    insertionSort(nums);

    std::cout << "排序后：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们在 `insertion_sort.h` 头文件中声明了一个模板函数 `insertionSort`，该函数可以接受任意类型的 `std::vector` 参数。然后，在 `insertion_sort.cpp` 源文件中，我们实现了模板函数 `insertionSort` 的具体逻辑，并使用 `template` 关键字进行了显式实例化，以便在编译时生成特定类型的代码。

在 `main.cpp` 主程序文件中，我们包含了 `insertion_sort.h` 头文件，并调用了 `insertionSort` 函数对 `std::vector<int>` 类型的数组进行排序。

要编译这些文件，可以使用以下命令：

g++ main.cpp insertion_sort.cpp -o main

然后运行生成的可执行文件 `main`，就可以看到排序前后的结果输出。