七日算法先导(三)—— 冒泡排序,选择排序
2023-02-18 16:27:09 时间
作业解答
class Solution {
public int[] twoSum(int[] numbers, int target) {
//递减,满足相加之和为target
for (int i = 0, j = numbers.length - 1; i < j;) {
int sum = numbers[i] + numbers[j];
if (sum == target) return new int[] {i + 1, j + 1};
else if (sum > target) j--;//大了,向左移动
else i++;//小了,向右移动
}
return null;
}
}
#include<iostream>
using namespace std;
int n,a[1001];
int main()
{
cin>>n;//输入
for(int i=1;i<=n;i++)cin>>a[i];//和输入
sort(a+1,a+n+1);//和排序
for(int i=1;i<=n/2;i++)
{
cout<<a[n-i+1]<<endl<<a[i]<<endl;//和输出
}
if(n%2)cout<<a[n/2+1]<<endl;//和判定
}
概念
排序,不同的算法书,有不同的解答,有的叫10大排序,有的叫8大排序,我们是按照十个来讲, 具体可以看下面这篇我早期写的文章:10大排序
冒泡排序
思想: 俩俩比较,如果反序交换,直到没有反序的记录为止,代码实现比较简单,是俩个for循环的嵌套
#include<iostream>
#include<algorithm>//调用算法库,使用交换函数swap
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
for (int j = i + 1; j < 10; j++)
{
if (a[i] < a[j])
swap(a[i], a[j]);
}
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}
时间复杂度为O(n^2)
选择排序
我们发现,从第一个元素到最后一个元素中选择出一个最小的元素,和第一个元素进行交换,然后,从第二个元素到最后一个元素中选择出最小的元素,和第二个元素进行交换,最后,一定可以保证所有元素都是升序排列的
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
int min = i;
for (int j = i + 1; j < 10; j++)
{
if (a[min] > a[j])
min = j;//交换下标位置
}
if (i != min)
swap(a[i], a[min]);
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}
刷题巩固
相关文章
- 多云架构下,JAVA微服务技术选型实例解析
- JAVA已过气?中俄大佬对话告诉你俄罗斯最受欢迎的编程语言是什么!
- Acrobat最经典的版本:PDF编辑器Acrobat 2021经典版,下载
- Adobe Acrobat Pro DC 2019(PDF) 软件下载安装包教程(附下载方法)
- Adobe Acrobat Pro DC 2018(PDF) 软件下载安装包教程(附下载方法)
- 仅需1% Embedding参数,硬件成本降低十倍,开源方案单GPU训练超大推荐模型
- 文件更小,质量更高,大火的Stable Diffusion还能压缩图像?
- 11分钟充电70%,华人教授在锂电池中加镍箔登上Nature
- 戴着VR头盔教机器人抓握,机器人当场就学会了
- 还未入职,这位将来的博导为学生规划了一条高效学习之路
- 英特尔i9-13900K重夺PC性能桂冠:与AMD 7950X拉开8%差距
- 价值1亿美金时,Stable Diffusion背后的团队开始互撕,谁才是真官方?
- NeurIPS 2022 | 用变分编码器生成周期图,时间、空间复杂度最低
- Bengio、LeCun 等人联名上书,呼吁美国投资神经AI,攻破「具身图灵测试」
- 30亿跑赢GPT-3的1750亿,谷歌新模型引热议,然而却把Hinton年龄搞错了
- Stable Diffusion新玩法,一句话帮你换图,网友魔改《戴珍珠耳环的少女》长这样
- LeCun转推,PyTorch GPU内存分配有了火焰图可视化工具
- ECCV 2022 | 摆脱部件标签依赖,上科大&ZMO.AI提出分部件3D人体重建与驱动新方法UNIF
- 清华作者排名第一,多人中稿超十篇:NeurIPS 2022统计数据出炉
- Transformer作者离职创业的公司,想从老东家谷歌再拿2亿美元融资