冒泡排序(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