数据结构——排序之冒泡排序

💞💞 前言

hello hello~ ，这里是大耳朵土土垚~💖💖 ，欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹

💥个人主页：大耳朵土土垚的博客
💥 所属专栏：数据结构学习笔记、排序算法合集
💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习过四种排序——直接插入排序、希尔排序、直接选择排序和堆排序，今天我们就来学习交换排序的一种——冒泡排序。

1.什么是冒泡排序？

冒泡排序（BubbleSort）是一种计算机科学领域的较简单的排序算法。它的基本思想是通过重复遍历待排序的数据集，并依次比较相邻的两个数据项，如果它们的顺序错误则进行交换。这个过程会持续重复直到所有相邻的数据项都已经交换完毕，此时说明该数据集已经排好序。冒泡排序的名称来源于排序过程中，较小的数据项会被逐渐“浮”到数组顶部，这个过程就像碳酸饮料中二氧化碳气泡最终会上浮到顶部的现象一样。因此，这种排序算法因其这一特性而得名。

冒泡函数的核心思想就是：两两相邻的元素进行比较，一轮下来最大的或者最小的就会被交换到最后面，每一轮都得到该轮的最值排到后面，如果是升序就得到最大值，降序就是最小值，排n轮直到有序。

如下动图演示：

在这里插入图片描述

2.冒泡排序代码实现（升序）

2.1基础版（升序）

void bubble_sort(int arr[], int sz)//参数接收数组元素个数{for(int i=0; i<sz-1; i++)//排sz-1趟{for(int j=0; j<sz-i-1; j++)//一趟排序{if(arr[j] > arr[j+1])//前面的大就交换到后面，直到最后得到升序{//交换int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}}
//打印数据 
int main(){int arr[] = {3,1,7,5,8,9,0,2,4,6};int sz = sizeof(arr)/sizeof(arr[0]);bubble_sort(arr, sz);for(int i=0; i<sz; i++){printf("%d ", arr[i]);}return 0;}

这里注意使用两层for循环嵌套来实现，一层用来实现一趟排序所要进行的步骤，最外层for循环则表示这样的步骤要实现size-1次才能得到有序，每一趟排序都得到最值，排到后面，直到有序。

结果如下：
在这里插入图片描述

2.2进阶版（升序）

进阶实现：

我们发现上述代码即使在排序过程中有序了，该跑size-1趟还是不会少，它才不管你有没有序，我只要跑我的size-1趟就好了，这样就会大大消耗我们的时间，所以我们的想个方法一旦它有序冒泡排序就停下；

解决思路：

我们可以思考它什么是会有序呢？是不是一趟下来什么都没交换这样就可以判定为有序了，所以我们可以使用一个变量flag来标记。代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void bubble_sort(int arr[], int sz)//参数接收数组元素个数{for (int i = 0; i < sz - 1; i++)//排sz-1趟{int flag = 0;//没趟排序开始flag清0for (int j = 0; j < sz - i - 1; j++)//一趟排序{if (arr[j] > arr[j + 1])//前面的大就交换到后面，直到最后得到升序{flag++;//有交换flag就++//交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}//一趟排序后查看flag值if (flag == 0)//如果flag = 0 ，也就是没有发生交换直接return即可return;}}
//打印数据 
int main(){int arr[] = {9,1,2,3,4,5,6,7,8};int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;}

将flag设在每趟排序里面，如果有交换flag就++；没有flag值就是0说明此时有序可以直接返回；注意不要忘了每趟排序完flag都要清0哦~不然下次使用即时没有发生交换flag也不为0；

使用int arr[] = {9,1,2,3,4,5,6,7,8};来测试结果如下：
在这里插入图片描述

3.冒泡排序代码实现（降序）

学习完升序，降序对我们来说简直是老虎吃豆芽——小菜一碟，只需将交换的条件由大于改成小于号即可

if (arr[j] < arr[j + 1])//前面的小就交换到后面，直到最后得到升序

完整代码实现如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void bubble_sort(int arr[], int sz)//参数接收数组元素个数{for (int i = 0; i < sz - 1; i++)//排sz-1趟{int flag = 0;//没趟排序开始flag清0for (int j = 0; j < sz - i - 1; j++)//一趟排序{if (arr[j] < arr[j + 1])//前面的小就交换到后面，直到最后得到升序{flag++;//有交换flag就++//交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}//一趟排序后查看flag值if (flag == 0)//如果flag = 0 ，也就是没有发生交换直接return即可return;}}
//打印数据 
int main(){int arr[] = {9,1,2,3,4,5,6,7,8};int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;}

结果如下：
在这里插入图片描述

4.冒泡排序时间复杂度分析

时间复杂度往往分析最坏的情况，所以在分析冒泡排序时我们可以当作冒泡了size-1次，假设有n个数，也就是n-1次，每次又两两相比较，第一次比较n-1下，第二次n-2…最后一次1下，将这n-1次加起来就可以知道冒泡排序的时间复杂度啦~ 利用等差数列求和很容易算出来结果并区取最大的数量级n^2即可；
🥳🥳所以冒泡排序的时间复杂度是O(n^2)