当前位置：首页 > news >正文

C++菜鸟教程 - 从入门到精通第五节

news 来源：原创 2025/7/29 7:37:13

一.各种排序

接下来,让我们开始学习排序!

1.选择排序

a.原理简介

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾，直到所有元素排序完成。

选择排序的步骤：
1. 初始化：假设数组的第一个元素是最小的。
2. 查找最小值：遍历未排序部分，找到最小的元素。
3. 交换：将找到的最小元素与未排序部分的第一个元素交换。
4. 重复：重复上述步骤，每次从未排序部分选择最小元素，直到所有元素排序完成。

b.时间\空间复杂度

时间复杂度：
最好情况：O(n²)
最坏情况：O(n²)
平均情况：O(n²)

选择排序的时间复杂度为O(n²)，因为它需要进行n次遍历，每次遍历需要比较n-i次（i为当前遍历的次数）。

空间复杂度：
O(1)，因为它是原地排序，不需要额外的存储空间。

c.优缺点

优点：简单易实现，适合小规模数据。
缺点：效率低，不适合大规模数据。

选择排序虽然简单，但在处理大规模数据时效率较低，通常用于教学或小规模数据的排序场景。

d.代码示范

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1e5+1;
int n,a[N],in; 
void PrintArray(int a[],int n){for(int i=1;i<=n;i++){cout<<a[i]<<" "; } 
} 
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]); }for(int i=1;i<=n-1;i++){in=i;for(int j=i+1;j<=n;j++){if(a[j]<a[in]){in=j; }			} swap(a[in],a[i]);} PrintArray(a,n);return 0;
}

2.桶排序

a.原理简介

桶排序（Bucket Sort）是一种分布式排序算法，它将一个数组分到有限数量的桶里。每个桶再分别进行排序，最后将各个桶中的数据合并，得到排序后的结果。‌

桶排序的基本思想是将数据分配到有限数量的桶中，每个桶再分别进行排序。具体步骤如下：

‌分配‌：将数据均匀地分配到各个桶中。
‌排序‌：对每个桶中的数据进行排序。
‌合并‌：将各个桶中的数据合并成一个有序序列。

b.时间\空间复杂度

时间复杂度‌：在平均情况下，桶排序的时间复杂度为O(n)，其中n是待排序数据的数量。这是因为每个桶内的数据量相对较少，可以快速排序。然而，在最坏情况下，时间复杂度可能接近O(n^2)，这取决于桶内排序算法的选择和数据的分布情况。‌

空间复杂度‌：桶排序的空间复杂度主要取决于桶的数量。如果使用额外的存储空间来存储桶中的数据，则空间复杂度为O(n+k)，其中k是桶的数量。如果使用原地算法，则空间复杂度为O(1)。‌

c.优缺点

优点‌：
‌效率高‌：在数据分布均匀的情况下，桶排序的效率非常高，接近线性时间复杂度。
‌适合大数据量‌：对于大数据量的排序问题，桶排序可以显著提高效率。

‌缺点‌：
‌依赖数据分布‌：如果数据分布不均匀，某些桶可能会包含大量数据，导致某些桶内的排序时间变长，影响整体效率。
‌需要额外空间‌：如果使用额外的存储空间来存储桶中的数据，则需要额外的内存开销。

d.代码示范

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],t,Max; 
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&t);a[t]=1;Max=max(Max,t); } for(int i=1;i<=Max;i++){if(a[i]) cout<<i<<" "; } return 0;
}

3.sort排序

在C++中，sort是一个标准库函数，用于对容器中的元素进行排序。sort函数使用快速排序算法，其时间复杂度为O(n log n)。sort函数通常用于对数组和STL容器（如vector、deque、list等）进行排序。下面是一个简单的示例，使用sort函数对一个整数数组进行升序排序：

#include <iostream>
#include <algorithm>int main() {int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};int n = sizeof(arr) / sizeof(arr[0]);std::sort(arr, arr + n);std::cout << "Sorted array: ";for (int i = 0; i < n; i++) {std::cout << arr[i] << " ";}return 0;
}

在上面的示例中，std::sort(arr, arr + n)将整数数组arr进行升序排序。排序后的结果将被打印出来。

除了默认的升序排序，sort函数还支持自定义排序规则。可以通过传递自定义的比较函数来实现按照特定的顺序进行排序，比如逆序排序或者按照某个成员变量进行排序。

好的,我们在这里就不做赘述,还想看更多排序?

点击链接!

https://blog.csdn.net/C_User1024/article/details/139566339?sharetype=blogdetail&sharerId=139566339&sharerefer=PC&sharesource=C_User1024&spm=1011.2480.3001.8118https://blog.csdn.net/C_User1024/article/details/139566339?sharetype=blogdetail&sharerId=139566339&sharerefer=PC&sharesource=C_User1024&spm=1011.2480.3001.8118

二.struct结构体

1.struct简介

在C++中，struct（结构体）是一种用户定义的数据类型，用于将不同类型的数据组合在一起。它类似于class，但默认的访问权限是public，而class的默认访问权限是private。

2.struct如何定义

你可以使用`struct`关键字来定义一个结构体，并在其中声明多个成员变量。例如：

struct Person {std::string name;             //字符串值int age;                      //整形值double height;                //高精度浮点值
};                    //不要忘记加分号,它和函数不一样

Person结构体包含了三个成员变量：name（字符串类型）、age（整数类型）和 height（双精度浮点数类型)

3.调用struct

仍以上面的Person结构体为例.

Person person1;
person1.name="Steve";
person1.age=30;
person1.height=1.65;
cout<<"Name: " << person1.name << ", Age: " << person1.age << ", Height: " << person1.height<<endl;

使用:

结构体名称 . 参数

即可调用结构体

创建了一个复合数据变量,

将参数name设为"Steve"

将参数age设为30

将参数height设为1.65

struct是C++中用于组合不同类型数据的工具，适合简单的数据封装。它与`class`非常相似，但在默认访问权限和继承方式上有所不同。

三.高精度加法

1.高精度算法简介

高精度算法是一种用于进行大数运算的算法，通过使用特定的数据结构和计算方法来实现对高精度数字的精确计算。在传统的计算机中，通常对固定范围的数值进行运算，而高精度算法则允许处理更大范围的数字，甚至可以处理超过计算机标准数据类型所能表示的整数或小数。高精度算法通常用于解决需要极高计算精度的问题，如大整数运算、高精度小数运算、密码学算法等。

高精度算法通常基于大数运算的原理，其中常用的数据结构包括大整数（BigInteger）和大浮点数（BigDecimal）。

在进行高精度计算时，算法通常采用分治法、动态规划等高效算法来提高计算效率。此外，高精度算法还需要考虑处理数据的进位、借位、溢出等问题，以保证计算结果的准确性。

2.高精度加法的原理

高精度加法是指在进行数值计算时，对于较大的数字或小数精确度要求较高的情况下，采用特定的算法进行加法运算，以保证计算结果的准确性。其原理主要涉及以下几个方面：

1. 数据存储

对于较大数字或小数，可能会超出计算机内置数据类型的表示范围，因此需要采用特定的数据结构（如数组或链表）来存储数字，以保证精度和长度的可扩展性。

2. 对齐位数

在进行高精度加法时，需要将参与运算的数字对齐到同一位数，通常是保证小数点对齐，或者在整数部分前补零，以便逐位相加。

3. 逐位相加

从最低位（个位或小数点后第一位）开始逐位相加，将进位考虑在内，直到最高位得到最终结果。

4. 进位处理

在逐位相加的过程中，需要考虑进位的情况。如果某一位相加后值大于等于基数（10或2，取决于进制），则需要将进位加到高一位。这样可以确保每一位的运算都是在同一基数下进行的。

5. 结果展示

最终得到的结果需要根据实际情况进行格式化展示，包括去除前导零、确定小数点位置等。

3.编写高精度加法的步骤

1.变量的定义

需要如下变量(变量名可自行修改)
const int N=1e5+10;
char s1[N],s2[N];
int a[N],b[N],c[N],lena,lenb,MAX,x;
N : 数组大小,可进行调整

s1,s2 : 进行高精度加法的两个数

a,b : s1,s2的倒序

c : 计算结果的倒序

lena,lenb : 进行高精度加法的两个数的长度

MAX : 最大位数

x : 进位

2.输入,倒序

cin>>s1>>s2;
lena=strlen(s1);
lenb=strlen(s2);
MAX=max(lena,lenb);
for(int i=0;i<lena;i++) a[i]=s1[lena-1-i]-'0'; 
for(int i=0;i<lenb;i++) b[i]=s2[lenb-1-i]-'0';

3.计算

for(int i=0;i<MAX;i++){        //遍历c[i]=a[i]+b[i]+x;          //计算x=c[i]/10;                 //进位处理c[i]%=10;                  
} 
if(x) c[MAX++]=x;              //最后进位处理

4.倒序输出

for(int i=MAX-1;i>=0;i--){cout<<c[i]; 
}

完整代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
char s1[N],s2[N];
int a[N],b[N],c[N],lena,lenb,MAX,x;
int main(){cin>>s1>>s2;lena=strlen(s1);lenb=strlen(s2);MAX=max(lena,lenb);for(int i=0;i<lena;i++) a[i]=s1[lena-1-i]-'0'; for(int i=0;i<lenb;i++) b[i]=s2[lenb-1-i]-'0';for(int i=0;i<MAX;i++){c[i]=a[i]+b[i]+x;x=c[i]/10;c[i]%=10;} if(x) c[MAX++]=x; for(int i=MAX-1;i>=0;i--){cout<<c[i]; } return 0;
}

四.题目测试

救援争先

内存限制: 256 Mb

时间限制: 1000 ms

题目描述

某地出现了灾害，各地派出了 n 只救援队。这些救援队是在同一天出发的，但出发时间不一样，路程也有长有短，所以达到时间有先有后。

给定每个队伍的出发时间，以及每只队伍的路程，请按照到达时间为这些队伍排序，如果多只队伍的到达时间正好相等，则出发时间靠前的队伍排在前列，如果出发时间仍然相等，则编号较小的队伍排在前列。

输入格式

第一行：单个整数 n，表示救援队数量。
第二行到第 n+1 行：在第 i+1 行，有两个时间，表示第 i 只救援队的出发时间和到达时间，数据格式均为 hh:mm

hh 表示小时，在 00 到 23 之间；
mm 表示分钟，在 00 到 59 之间。

输出格式

共 n 行，每行一个整数，按救援队到达的先后顺序输出它们的编号。

数据范围

1≤n≤1000

题目分析

1.首先,要存储救援队的出发时间,路程,编号 ( 用结构体最合适 )

需含有出发,结束时间,编号

2.要先看到达时间是否相等,若相等,看出发时间,若依然相等,就按编号比较

使用sort方便一些

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,sh,sm,lh,lm;
struct Boat{int begin,end,index;
};
Boat boats[1001]; 
bool cmp(Boat b1,Boat b2){if(b1.end==b2.end){if(b1.begin==b2.begin){return b1.index<b2.index;} return b1.begin<b2.begin;} return b1.end<b2.end;
} 
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d:%d %d:%d",&sh,&sm,&lh,&lm); boats[i].begin=sh*60+sm;boats[i].end=boats[i].begin+lh*60+lm;boats[i].index=i; } sort(boats+1,boats+1+n,cmp); for(int i=1;i<=n;i++){cout<<boats[i].index<<endl; } return 0;
}

其中的cmp是一个排序函数,返回的是排序的升\倒序

好了,今天的教学就到这里了 ,把你想学的打在评论区,我们不见不散!

一.各种排序

1.选择排序

a.原理简介

b.时间\空间复杂度

c.优缺点

d.代码示范

2.桶排序

a.原理简介

b.时间\空间复杂度

c.优缺点

3.sort排序

二.struct结构体

1.struct简介

2.struct如何定义

3.调用struct

三.高精度加法

1.高精度算法简介

2.高精度加法的原理

1. 数据存储

2. 对齐位数

3. 逐位相加

4. 进位处理

5. 结果展示

3.编写高精度加法的步骤

1.变量的定义

2.输入,倒序

3.计算

4.倒序输出

完整代码

四.题目测试

救援争先

题目描述

输入格式

输出格式

数据范围

题目分析

代码

相关文章：