[C 语言] 深入了解气泡排序算法（优化 + 详解）
文章目录
- 什么叫冒泡排序？
- 图解冒泡排序
- 第一轮排序
- 第二轮排序
- 第三轮排序
- 第四轮排序
- 第五轮排序
- 第六轮排序
- 第七轮排序
- 第八轮排序
- 代码实现
- 代码优化
什么叫冒泡排序？
冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。
整个过程如同气泡冒起，因此被称作冒泡排序。
通俗来说，也就是：
从第一个元素开始比较相邻的两个元素，如果第一个比第一个大或小，就互换它们的位置，这样先比较完一次，然后抛弃最大或最小的继续比较，直到排序完成。
冒泡排序的步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
- 针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。
动画演示：
此处引用网上一张比较经典的gif来展示冒泡排序的整个过程：
图解冒泡排序
有8个数组组成一个无序数列：5,8,6,3,9,2,1,7，希望从小到大排序。
按照冒泡排序的思想：把相邻的两个数字两两比较，当一个数字大于右侧相邻的数字时，交换他们的位置，当一个数字和他右侧的数字小于或等于的时候，不交换。
第一轮排序
- 首先让5和8进行交换，发现5比8小，因此元素位置不变；
- 接下来让8和6比较，发现8比6大，所以要交换8和6的位置；
- 继续让8和3比较，发现8比3要大，所以8和3 交换位置；
- 继续让8和9进行比较，发现8比9小，不用交换；
- 9和2进行比较，发现9比2大，进行交换；
- 继续让9和1进行比较，发现9比1大，所以交换9和1的位置；
- 最后，让9和7交换位置；
这样一来，元素9作为数列的最大元素，就已经排序好了
第二轮排序
- 首先让5和6比较，发现5比6小，位置不变；
- 接下来让6和3比较，发现6比3大，交换位置；
- 接下来让6和8比较，6比8小，位置不变；
- 8和2比较。8比2大，交换位置；
- 接下来让8和1比较，8比1大，因此交换位置；
- 继续让8和7比较，发现8比7大，交换位置；
这样一来，第二轮排序已经好了
第三轮排序
按照以上步骤，可得第三轮排序：
第四轮排序
按照以上步骤，可得第四轮排序：
第五轮排序
按照以上步骤，可得第五轮排序：
第六轮排序
按照以上步骤，可得第六轮排序：
第七轮排序
按照以上步骤，可得第七轮排序，此时已经有序了：
第八轮排序
此时已经排序完成啦！
到此为止，所有的数字都是有序的了，冒泡排序是一种稳定排序，由于该排序算法的每一轮都要遍历所有的数字，一共要遍历n-1，所以时间复杂度为：O(n^2)
那么我们如何区分排序算法是否稳定呢？
如果我们交换的时候，遇到两个相同的数字；
如果两个相同的数字在排序之后相对位置没有交换，那么就是稳定的排序，反之则是不稳定的排序。
代码实现
代码过程如下：
void bubble_sort(int* arr, int sz) { int i = 0; int j = 0; for (i = 0; i < sz - 1; i++) { 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; } } } } int main() { int arr[10] = { 5, 8, 6, 3, 9, 2, 1, 7 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz); int i = 0; for (i = 0; i < 10; i++) { printf("%d ", arr[i]); } }
运行结果：
这个代码很简单，使用双循环的方式进行排序。
外部的循环控制所有回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。
代码优化
从上面的例子不难看出，我们可以对原来的冒泡排序进行优化。
我们仍然用上面呢个数列{ 5, 8, 6, 3, 9, 2, 1, 7 }为例子，从上面的图解可以看出在第六、第七、第八轮排序后，整个数列已经是有序的了，但是排序算法还是执行到了第八轮排序。