[已解决]求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++的插入排序代码。以下是一个简单的插入排序的实现：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void insertionSort(int arr[], int n) {
   
5.     for (int i = 1; i < n; i++) {
   
6.         int key = arr[ i];
   
7.         int j = i - 1;
   
8. 
   
9.         while (j >= 0 && arr[j] > key) {
   
10.             arr[j + 1] = arr[j];
    
11.             j--;
    
12.         }
    
13.         arr[j + 1] = key;
    
14.     }
    
15. }
    
16. 
    
17. int main() {
    
18.     int arr[] = {5, 2, 4, 6, 1, 3};
    
19.     int n = sizeof(arr) / sizeof(arr[0]);
    
20. 
    
21.     insertionSort(arr, n);
    
22. 
    
23.     cout << "插入排序后的数组：";
    
24.     for (int i = 0; i < n; i++) {
    
25.         cout << arr[ i] << " ";
    
26.     }
    
27.     cout << endl;
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

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

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

isdkz

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

1. #include <iostream>
   
2. 
   
3. void insertionSort(int arr[], int n) {
   
4.     for (int i = 1; i < n; ++i) {
   
5.         int key = arr[ i];
   
6.         int j = i - 1;
   
7. 
   
8.         while (j >= 0 && arr[j] > key) {
   
9.             arr[j + 1] = arr[j];
   
10.             j = j - 1;
    
11.         }
    
12.         arr[j + 1] = key;
    
13.     }
    
14. }
    
15. 
    
16. int main() {
    
17.     int arr[] = {12, 11, 13, 5, 6};
    
18.     int n = sizeof(arr) / sizeof(arr[0]);
    
19. 
    
20.     std::cout << "排序前的数组：" << std::endl;
    
21.     for (int i = 0; i < n; ++i) {
    
22.         std::cout << arr[ i] << " ";
    
23.     }
    
24. 
    
25.     insertionSort(arr, n);
    
26. 
    
27.     std::cout << "\n排序后的数组：" << std::endl;
    
28.     for (int i = 0; i < n; ++i) {
    
29.         std::cout << arr[ i] << " ";
    
30.     }
    
31. 
    
32.     return 0;
    
33. }
    

复制代码

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

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

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

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

Mike_python小

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

2. #include <iostream>
3. using namespace std;
5. void insertionSort(int arr[], int n) {
6.     for (int i = 1; i < n; i++) {
7.         int key = arr[i];
8.         int j = i - 1;
10.         while (j >= 0 && arr[j] > key) {
11.             arr[j + 1] = arr[j];
12.             j--;
13.         }
15.         arr[j + 1] = key;
16.     }
17. }
19. int main() {
20.     int arr[] = {5, 2, 8, 12, 3};
21.     int n = sizeof(arr) / sizeof(arr[0]);
23.     cout << "排序前的数组：" << endl;
24.     for (int i = 0; i < n; i++) {
25.         cout << arr[i] << " ";
26.     }
27.     cout << endl;
29.     insertionSort(arr, n);
31.     cout << "排序后的数组：" << endl;
32.     for (int i = 0; i < n; i++) {
33.         cout << arr[i] << " ";
34.     }
35.     cout << endl;
37.     return 0;
38. }

复制代码

这段代码实现了插入排序算法。通过调用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

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int main()
   
8. {
   
9.     int n;
   
10.     cin >> n;
    
11.     vector<int> temp_array(n);
    
12.     for(int i = 0; i < n; i++)
    
13.     {
    
14.         cin >> temp_array[i];
    
15.     }
    
16.     sort(temp_array.begin(), temp_array.end());
    
17.     for(int i = 0; i < n; i++)
    
18.     {
    
19.         cout << temp_array[i] << " ";
    
20.     }
    
21.     cout << endl;
    
22.     return 0;
    
23. }

复制代码

就是用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育碧了

谢