SCS_user_EHQ0z2l6el查看:29 回复:6 评论:29 创建时间:2023-05-02T21:41:47用户:SCS_user_EHQ0z2l6el查看:29 回复:6 评论:29 创建时间:2023-05-02T21:41:47
可怜娃子
虽然这次我要讲的不是桶排（）
但是给了我出新教程的灵感）
这次我们将要学习基础排序算法：
冒泡排序
什么是排序
排序，顾名思义是将一堆数据排列成有序的
例如把[3,1,4,5,1,4,9,2,6]
扔进排序算法里就能排列成有序的组合（以下排序皆为按从小到大的顺序排序）
[1,1,4,5（吡——）
[1,1,2,3,4,4,5,6,9]
在算法的海洋里存在着许多排序的算法
例如前面提到的冒泡
还有快速排序、归并排序、堆排序、鸡尾酒排序（你没看错）、希尔排序、计数排序、桶排序等等
然而有人可能要说：“明明一个算法就够用了，为什么还要有这么多算法呢？”
就像有人喜欢黑的，有人喜欢白的，也有人喜欢无添加的
仅仅巧克力而言就有如此多的选择
更何况是算法
各个算法有各自的优势
比如计数排序，在数据分配均匀的情况下速度可以达到线性的时间复杂度
另外
排序分为稳定排序和不稳定排序
例如下面的输入
[4,1,1,5]
稳定排序 [1,1,4,5]
不稳定排序[1,1,4,5]
看得出有什么变化吗
稳定排序的第一个1排序过后始终是第一个
不稳定排序的第一个1排序过后就不是第一个了
稳定排序排序前后两个相等的数相对位置不变
不稳定排序排序前后两个相等的数相对位置发生了变化
冒泡排序
整体思路
冒泡排序是最基础的算法之一，它差不多是从缺少灵魂迈进给予灵魂（众所周知，代码的灵魂是算法的美称）
冒泡，顾名思义，是一层一层往上冒
差不多是冒泡排序的思想
首先它遍历整个数组，依次比较两个相邻的元素，如果顺序不一致就交换
比如
3 1 4 1 5
比较3和1，发现3>1，于是3和1互换
1 3 4 1 5
比较3和4，发现3<4，所以他们顺序不变
1 3 4 1 5
比较4和1，发现4>1，于是4和1互换
1 3 1 4 5
比较4和5，发现4<5，所以他们顺序不变
这就是冒泡排序的第一轮
第二轮也是一样
1 3 1 4 5
比较3和1，发现1<3，所以他们顺序不变
1 3 1 4 5
比较3和1，发现3>1，于是3和1互换
1 1 3 4 5
比较3和4，发现3<4，所以他们顺序不变
但是遍历到第三个元素和第四个元素之后就结束了
其原因是一轮冒泡过后冒泡过的数据的最后一个就是最大的
就拿上面那轮举例
第一轮结束时最后一个是1 3 1 4 5中最大的
第二轮结束时倒数第二个是1 1 3 4中最大的
第三轮结束时倒数第三个是1 1 3中最大的
以此类推
最终比较到第五轮只剩下1一个元素，不用排序
数组里的元素在比较完之后就是有序的[1,1,3,4,5]
冒泡算法的时间复杂度和空间复杂度
由于冒泡排序是原地排序，并没有借助任何空间，所以他的空间复杂度是O(0)
冒泡排序的时间复杂度很好算
首先它要进行(n-1)次遍历，从比较(n-1)个元素到比较1个元素
也就是(n-1)+(n-2)+(n-3)+......+1
=(n-1+1)(n-1-1+1)/2
=n(n-1)/2
=1/2n的平方-1/2n
选取最高项并舍去系数就是n的平方
所以冒泡排序的时间复杂度是n的平方（推的过程可能有问题）
好了，有关排序、冒泡的内容我就讲到这里了
感兴趣的朋友可以去翻我之前的教学帖
也可以翻翻评论区看我有没有写代码）
再见awa
SCS_user_EHQ0z2l6el
#include<iostream>
using namespace std;
int main(){
int a[1000],n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1])swap(a[j],a[j+1]);
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}点赞0
评论
神射手会记事本
#include<iostream>
using namespace std;
int main(){
int a[1001],n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
cout << a[i];
return 0;
}
//sort排序函数，从小到大点赞0
评论