目录
前言
冒泡排序算法是必须掌握的一种基础算法，在一些比较出名的竞赛可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解冒泡排序算法。
一、什么是冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，其基本思想是通过多次遍历待排序的数列，比较相邻元素的值，并在必要时交换它们的位置，从而将最大的元素逐步“冒泡”到数列的末尾。这个过程会重复进行，直到整个数列有序为止。
二、冒泡排序的的基本步骤
1.初始化：设定一个标志位（通常是布尔值），用于优化算法（可选）。
2.遍历数列：从数列的第一个元素开始，到倒数第二个元素结束。
3.比较和交换：
比较相邻的两个元素。
如果前一个元素比后一个元素大（对于升序排序），则交换它们的位置。
4.优化（可选）：如果在一次完整的遍历中没有发生任何交换，说明数列已经有序，可以提前结束排序。
5.重复：重复步骤2到步骤4，直到没有需要交换的元素为止。
三、冒泡排序的特点
时间复杂度：
最好情况：O(n)（数组已经有序时，通过优化可以提前结束）
最坏情况：O(n^2)（数组完全逆序时）
平均情况：O(n^2)
空间复杂度：O(1)（原地排序，不需要额外的存储空间）
稳定性：冒泡排序是稳定的排序算法，即相等元素的相对顺序在排序前后不会改变。
尽管冒泡排序的时间复杂度较高，但其实现简单，对于小规模数据或特定场景下的简单排序任务，仍然有一定的应用价值。
四、冒泡排序算法图解
五、经典例题
1.合并两个有序数组
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
nums1.resize(m);
for(int i=0;i<n;i++){
int x=nums2[i];
nums1.push_back(x);//将nums2数组插入nums1中
}
for(int i=nums1.size()-1;i>=0;i--){//我这个是往前冒，就是把最小值放前面
for(int j=0;j<i;j++){
if(nums1[j+1]<nums1[j]){
int t=nums1[j+1];
nums1[j+1]=nums1[j];
nums1[j]=t;
}
}
}
}
};
2.元素计数
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
class Solution {
public:
int countElements(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[j]<nums[i]){
int t=nums[j];
nums[j]=nums[i];
nums[i]=t;
}
}
}
int cnt=0;
for(int i=1;i<nums.size()-1;i++){就是遍历除了第一个和最后一个，从1开始遍历到倒数第二个满足条件加1
if(nums[i]!=nums[0]&&nums[i]!=nums.back())cnt++;
}
return cnt;
}
};
3.最后一块石头的重量
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
class Solution {
void bubbleSort(vector<int>& stones){
for(int i=0;i<stones.size();i++){
for(int j=i+1;j<stones.size();j++){
if(stones[j]<stones[i]){
int t=stones[j];
stones[j]=stones[i];
stones[i]=t;
}
}
}
}
public:
int lastStoneWeight(vector<int>& stones) {
while(stones.size()>1){//直到石头数剩一个或零个结束
bubbleSort(stones);
int n=stones.size();//每次相减到都要排序一次
int v=stones[n-1]-stones[n-2];
stones.pop_back();
stones.pop_back();
if(v||stones.size()==0)stones.push_back(v);//这个过程结束结果就是数组第一个值，如果最后一次相减为0，就插入到数组，第一个值不能什么都没有
}
return stones[0];
}
};
六、结语
学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油。
希望各位帅哥点赞关注支持一下
