[已解决]求C++插入排序代码

香蕉那个不拿拿

如题
求助插入排序代码
chatgpt快上

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-7-28 20:57:40

香蕉那个不拿拿 发表于 2023-7-28 20:56
https://www.luogu.com.cn/problem/P1177

直接用sort吧。
参考https://fishc.com.cn/thread-220654-1-1.html

跳转到最佳答案楼层

陶远航

当然，我可以帮你提供C++的插入排序代码。以下是一个简单的插入排序的实现：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int 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 arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "插入排序后的数组：";
    for (int i = 0; i < n; i++) {
        cout << arr[ i] << " ";
    }
    cout << endl;

    return 0;
}

这段代码将一个整数数组进行插入排序并打印排序后的结果。在insertionSort函数中，我们使用了两个嵌套的循环。外部循环从第二个元素开始遍历到最后一个元素，内部循环将当前元素与它前面的元素进行比较，并将其插入到正确的位置。

希望这段代码能够满足你的需求，如果你对其中的任何部分有疑问，请随时向我提问。
如果问题已经解决，请设置最佳答案

isdkz

当然，以下是C++中插入排序的代码：

#include <iostream>

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

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "排序前的数组：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << arr[ i] << " ";
    }

    insertionSort(arr, n);

    std::cout << "\n排序后的数组：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << arr[ i] << " ";
    }

    return 0;
}

插入排序是一种简单直观的排序算法，它的基本思想是将数组分为已排序和未排序两部分。初始时，将第一个元素视为已排序部分，其余元素视为未排序部分。然后，从未排序部分逐个取出元素，插入到已排序部分的合适位置，直到未排序部分为空，排序完成。

代码中的 insertionSort 函数实现了插入排序算法，它采用嵌套循环的方式，外层循环用于遍历未排序部分，内层循环用于在已排序部分找到合适的插入位置。 key 变量用于暂存当前待插入的元素值，而 j 变量则是用来向前搜索合适位置的索引。

在 main 函数中，我们定义一个示例数组 arr ，然后调用 insertionSort 函数对其进行排序。最后，输出排序前后的数组元素，以验证排序是否正确进行。

请注意，这里只是演示代码，实际应用中，你可以根据需要将插入排序封装成函数，以便在其他地方重复使用。

Mike_python小

好的，下面是一个简单的C++插入排序代码示例：

#include <iostream>using namespace std;void insertionSort(int arr[], int n) {    for (int i = 1; i < n; i++) {        int 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 arr[] = {5, 2, 8, 12, 3};    int n = sizeof(arr) / sizeof(arr[0]);    cout << "排序前的数组：" << endl;    for (int i = 0; i < n; i++) {        cout << arr[i] << " ";    }    cout << endl;    insertionSort(arr, n);    cout << "排序后的数组：" << endl;    for (int i = 0; i < n; i++) {        cout << arr[i] << " ";    }    cout << endl;    return 0;}

这段代码实现了插入排序算法。通过调用insertionSort函数对给定的数组进行排序。在每一次迭代中，将当前元素与已排序的子数组比较，将较大的元素向右移动，然后将当前元素插入到正确的位置。

运行上述代码，将输出排序前后的数组：

[/code]
排序前的数组：
5 2 8 12 3
排序后的数组：
2 3 5 8 12
[/code]

希望这可以帮到你！如果有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

香蕉那个不拿拿

Mike_python小 发表于 2023-7-28 19:32
好的，下面是一个简单的C++插入排序代码示例：

        TLE超时

香蕉那个不拿拿

人工

香蕉那个不拿拿

这题
只能用sort函数吗

liuhongrun2022

香蕉那个不拿拿 发表于 2023-7-28 19:42
这题
只能用sort函数吗

题目发我

tommyyu

感觉要用快排
可以参考这里 -> https://fishc.com.cn/thread-220654-1-1.html

sfqxx

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> temp_array(n);
    for(int i = 0; i < n; i++)
    {
        cin >> temp_array[i];
    }
    sort(temp_array.begin(), temp_array.end());
    for(int i = 0; i < n; i++)
    {
        cout << temp_array[i] << " ";
    }
    cout << endl;
    return 0;
}

就是用sort，很简单

zhangjinxuan

归并排序，基数排序，只要时间复杂度在 O(n log n)左右或以下都可

算法没有唯一。

香蕉那个不拿拿

liuhongrun2022 发表于 2023-7-28 20:14
题目发我

https://www.luogu.com.cn/problem/P1177

tommyyu

香蕉那个不拿拿 发表于 2023-7-28 20:56
https://www.luogu.com.cn/problem/P1177

直接用sort吧。
参考https://fishc.com.cn/thread-220654-1-1.html

香蕉那个不拿拿

tommyyu 发表于 2023-7-28 20:57
直接用sort吧。
参考https://fishc.com.cn/thread-220654-1-1.html

用过，AC了，就是想试试插入，stl就是强

tommyyu

香蕉那个不拿拿 发表于 2023-7-28 21:05
用过，AC了，就是想试试插入，stl就是强

在https://fishc.com.cn/thread-220654-1-1.html中可以看到，插入的效率有一点低，不用stl可以试试别的（快排、冒泡）

sfqxx

就是不看我的，呵呵

香蕉那个不拿拿

sfqxx 发表于 2023-7-29 13:23
就是不看我的，呵呵

说的都挺好，给你评了3荣誉3育碧了

sfqxx

香蕉那个不拿拿 发表于 2023-7-29 13:55
说的都挺好，给你评了3荣誉3育碧了

谢