2025年冒泡排序

科技前沿 • 2025-03-21 23:51 • 阅读 50

大家好，我是讯享网，很高兴认识大家。

1.冒泡排序
首先冒泡排序是一种交换排序，通过比较相邻数字的大小，将大或者小的一方，逐次交换到最后或者最前端，本质是一种时间换空间的算法。
Bubblesort1
首先是未优化的算法
例如：5 4 3 2 1
我们需要由小到大的排序：一共要比较4+3+2+1 = 10次，交换
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5

3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
后面省略
时间复杂度： 外循环和内循环以及判断和交换元素的时间开销；
最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )；
最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O( n^2 )；
综上所述：
最优的时间复杂度为：O( n^2 ) ；有的说 O(n)，下面会分析这种情况；
最差的时间复杂度为：O( n^2 )；
平均的时间复杂度为：O( n^2 )；
空间复杂度：
空间复杂度就是在交换元素时那个临时变量所占的内存空间；
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；

Bubblesort2
首先是优化的算法

讯享网

我们在最里面的循环设置一个flag标志，一次内循环结束时，进行判断，如果flag不为1，说明没有进行交换，可以直接结束了。如果有交换那么，将flag 置0，继续比较。
我们可以看到下面的循环次数有明显的减少。
2.代码展示

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> int Bubblesort1(int* arr, int len) //冒泡排序 { 
    int count = 0; //为了对比优化后的次数 for (int i = 0; i <= len - 1; i++) { 
    for (int j = 1; j <= len - i - 1; j++) { 
    count++; if (arr[j - 1] > arr[j]) { 
    int tmp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = tmp; } } } return count; } int Bubblesort2(int* arr,int len) //冒泡排序优化 { 
    int count = 0; for (int i =0; i <= len-1; i++) { 
    int flag = 0; for (int j = 1; j <=len-i-1; j++) { 
    count++; if (arr[j-1] > arr[j ]) { 
    flag = 1; int tmp = arr[j-1]; arr[j-1] = arr[j ]; arr[j ] = tmp; } } if (flag == 0) { 
    break; } } return count; } void Print(int* arr, int len) { 
    for (int i = 0; i < len; i++) { 
    printf("%d ",arr[i]); } printf("\n"); } int main() { 
    int arr[] = { 
   4,8,9,10,11,12,13}; int len = sizeof(arr) / sizeof(arr[0]); Print(arr, len); int ret = Bubblesort1(arr,len); printf("%d\n", ret); Print(arr, len); int ret2 = Bubblesort2(arr, len); printf("%d\n",ret2); Print(arr, len); system("pause"); return 0; }

讯享网

3.结果展示

在这里插入图片描述
心得体会：冒泡排序是非常简单的排序，我们需要注意的是，优化代码让时间复杂度降低。

2025年冒泡排序

相关推荐