●🧑个人主页:你帅你先说.
●📃欢迎点赞👍关注💡收藏💖
●📖既选择了远方，便只顾风雨兼程。
●🤟欢迎大家有问题随时私信我！
●🧐版权：本文由[你帅你先说.]原创，CSDN首发，侵权必究。

🍎冒泡排序基本思想及其代码实现

冒泡排序也称气泡排序，是一种典型的交换排序方法，其基本思想是通过无序区中相邻元素关键字间的比较和位置的交换使关键字最小的元素如气泡一般逐渐往上"漂浮"直至"水面"。

🍉动图演示:

🍊图解冒泡排序过程:







这样，我们一趟冒泡排序就完成了，第二趟到第n趟都是这样两两比较来进行排序。
原理理解完了，该用代码来实现了，我们分析一下刚刚的过程，我们每一趟排序都会有一个最大值排在最后面，也就是说每一趟排序都会产生一个数在有序区，所以随着循环的推进，需要排序的数越来越少。
第一趟排序，需要排12个数，第一趟排序后，该趟排序的最大值排在了最后。
第二趟排序，需要排11个数，第一趟排序后，该趟排序的最大值排在了最后。
…
第n-1趟排序，需要排2个数，第一趟排序后，该趟排序的最大值排在了最后。
所以一共是排n-1趟，每趟排序需要比较的次数与趟数相依赖。
🍓代码实现:

void BubbleSort(int* arr, int sz)
{int i = 0;//冒泡排序的趟数for (i = 0; i < sz - 1; i++){//一趟冒泡排序的过程int j = 0;for (j = 0; j < sz-1-i; j++){if (arr[j] > arr[j + 1]){//交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}
}

到这里，基本的冒泡排序就写完了，但是这段代码还可以优化，我们设想一个场景，假如你要排的一组数全是有序的呢？那你还要排n-1趟，挺浪费时间的，所以我们可以做一个判断，如果这组数有序我们直接跳出循环。

void BubbleSort(int* arr, int sz)
{int i = 0;//冒泡排序的趟数for (i = 0; i < sz - 1; i++){//一趟冒泡排序的过程int j = 0;int flag = 1;//假设已经有序for (j = 0; j < sz-1-i; j++){if (arr[j] > arr[j + 1]){//交换int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;	}}if (flag == 1){break;}}
}

🍅算法分析:
第一趟排序比较了n-1次
第二趟比较了n-2次
…
第n-1趟比较了1次
根据等差数列公式我们可以算出
T(n) = $\frac{n\ast (n-1)}{2}$
所以时间复杂度为:O($n^2$)
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉
觉得写的不错可以给个一键三连 点赞👍关注💡收藏💖
🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉🍉