冒泡排序（Bubble Sort）是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序
冒泡排序_百度百科 (baidu.com)
冒泡排序适用于小规模数据和部分排序数据的情况，同时也常用于教学和理解排序算法的基本原理。
1. 算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
之后，针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2. 动图演示
3.代码实现
#include <stdio.h>
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
4.函数封装
升序排列
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{
uint8_t i=0,j=0;
uint16_t temp;
for(i=0;i<Count-1;i++)
{
for(j=0;j<Count-1-i;j++)
{
if(Data[j]>Data[j+1])
{
temp=Data[j];
Data[j]=Data[j+1];
Data[j+1]=temp;
}
}
}
}
降序排列
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{
uint8_t i=0,j=0;
uint16_t temp;
for(i=0;i<Count-1;i++)
{
for(j=0;j<Count-1-i;j++)
{
if(Data[j]<Data[j+1])//改变符号
{
temp=Data[j];
Data[j]=Data[j+1];
Data[j+1]=temp;
}
}
}
}
5.函数讲解
核心代码如下：
for(i=0;i<Count-1;i++) { for(j=0;j<Count-1-i;j++) { if(Data[j]>Data[j+1]) { temp=Data[j]; Data[j]=Data[j+1]; Data[j+1]=temp; } } }
外循环讲解
外循环其实就是已经排好的数据的个数累加过程.
i=0:一个也没有被确定，所以从0开始累加。
i<count-1:冒泡排序有Count个数，要从小到大排，内循环结束一次，就有一个数被确定,只要其中（Count-1）个较高位数的位置排好了，那么最小的数就排好了，比如三个大小不同的数，只要确定2个数，哪个最大，哪个第二大，那么第三个数就是最小。所以知道（Count-1）个较高位数的位置被确定，循环就结束。
i++：已知冒泡排序高位向后排，每一轮比较（内循环）都确定了一个最高位，这个最高位如果放在没有被排序的数里是最高位，这个最高位在已经确定位置的数里是最低位。
内循环讲解
j=0:从数组的第0个数开始遍历数组
j<count-i-1:Count个数据,需要比较（Count-1）次，而i是整个排序中被确定的数，一开始为0，每一次内结束循环结束就确定一个，就少比较i个数，所以在确定i个数的位置时，内循环需要比较的数据有（Count-i）个，数据要比较的次数为（Count-1-i）次
j++:相邻的相比较，所以加一
if条件语句为了升序比较，第一个与第二个，第二个与第三个…
if的花括号内就是C语言常用的交换位置的三个语句。
7.冒泡排序flag优化算法
冒泡排序还有一种优化算法，就是立一个 flag，当在一次数组遍历中元素没有发生交换，则证明该数组已经有序。但这种改进对于提升性能来说并没有什么太大作用。
解决方式：可以通过一个标志位来打断循环
void Bubble_Sort(uint16_t *Data,uint8_t Count)
{
uint8_t i=0,j=0,Flag=0;
uint16_t temp;
for(i=0;i<Count-1;i++)
{
for(j=0;j<Count-1-i;j++)
{
if(Data[j]>Data[j+1])
{
temp=Data[j];
Data[j]=Data[j+1];
Data[j+1]=temp;
Flag=1;
}
}
if(Flag==0)
{
break;
}
else
Flag=0;
}
}
8.时间复杂度分析
冒泡排序的时间复杂度分析是衡量算法效率的重要指标。我们来分析最好情况、最坏情况和平均情况下的时间复杂度：
最好情况：如果待排序的数组已经有序，即元素无需交换位置，那么只需要进行一次遍历，时间复杂度为 O(n)。
最坏情况：如果待排序的数组是逆序的，即每次比较都需要交换位置，那么需要进行 n-1 轮遍历，每轮遍历需要比较 n-i-1 次，时间复杂度为 O(n^2)。
平均情况：在平均情况下，需要进行 n/2 轮遍历，每轮遍历需要比较 n-i-1 次，时间复杂度也为
O(n^2)。
冒泡排序的时间复杂度为 O(n^2)，其中 n 表示待排序数组的长度。这说明随着数据规模的增大，冒泡排序的执行时间呈二次增长，效率较低。
9.性能分析
优点：
简单易懂：冒泡排序是一种非常简单的排序算法，它的思想容易理解，代码实现也相对容易。
稳定排序：冒泡排序是一种稳定的排序算法，即在排序过程中，相同大小的元素不会相互交换位置。
空间复杂度低：冒泡排序的空间复杂度为 O(1)，即它只需要使用固定的额外空间来存储交换的元素，而不依赖于输入数组的大小。
缺点：
时间复杂度高：冒泡排序的时间复杂度为 O(n^2)，在处理大规模数据时效率较低。
不适合大规模数据：由于冒泡排序需要进行多次比较和交换操作，对于大规模数据集，其性能可能会较差。
排序不彻底：在最坏情况下，冒泡排序可能无法将数组完全排序，例如当数组已经基本有序时。
10.总结
冒泡排序是最基础的排序算法之一，通过相邻元素的比较和交换，逐渐将最大（或最小）的元素冒泡到数列的一端。尽管冒泡排序的效率相对较低，但它的实现简单易懂，是理解排序算法的入门之选。
然而，在实际应用中，对于大规模数据集，我们更倾向于选择时间复杂度较低的排序算法，如快速排序、归并排序和堆排序等。这些算法能够在更短的时间内完成排序任务，提高程序的执行效率。因此，在实际开发中，我们需要根据具体情况选择合适的排序算法。
参考博客：
JS-Sorting-Algorithm/1.bubbleSort.md at master · hustcc/JS-Sorting-Algorithm · GitHub
【干货】深入剖析冒泡排序算法：原理、步骤与复杂度分析_冒泡算法-CSDN博客
版权归原作者 我不吃代码 所有， 如有侵权，请联系我们删除。