目录
1、缘起
2、BubbleSort 算法描述
3、用图示描述 BubbleSort 算法
4、C语言描述
5、Python语言描述
6、Java语言描述
7、总结
1、缘起
冒泡排序算法是一个非常经典的算法，它是各大网络编程平台上的座上宾，面试官口中的最爱。这个算法就是因其中数字从列表的开始向顶部移动的方式就像水泡从水中冒出的样子而得名，将较大的元素逐步"冒泡"到数组的顶部，从而实现排序。
虽然效率不如其他高级排序算法，但冒泡排序算法的思想易于理解和实现，是学习排序算法的入门良品。通过这篇博客让我们来翔实的了解一下冒泡排序算法吧 ！本篇博客所讲解的冒泡排序算法的排序为升序。
2、BubbleSort 算法描述
假设将需要排序的数字列表分成两个子列表:已排序的和未排序的。在未排序子列表中，最小的元素通过冒泡的方法选出来并移到已排序子列表中。
未排序子列表中的元素从前往后两两比较大小，如果一个元素比另外一个元素小，那么将这两个元素交换位置；否则，不进行任何处理，则进行下一次的元素两两比较；直到最大的元素排到合适的位置。最大元素排到合适的位置称之为一轮排序，一个含有N个元素的数字列表则需要 N-1轮来完成数据排序。
为什么是 N-1 轮排序？当未排序子列表剩下两个元素时，只需要交换一次数据，就完成了整个原始列表的数据排序。所以排序轮数比元素的个数少1。
3、用图示描述 BubbleSort 算法
注：红色方块左边为未排序元素，右边为已排序元素
第一轮，从 9 开始并把它与 5 比较，9 大于 5 则这两个元素进行位置交换。9 大于 7 则这两个元素进行位置交换。9 大于 1 则这两个元素进行位置交换。9 大于 3 则这两个元素进行位置交换，9 到达合适的位置。图中只给出了每一轮排序后的数字列表，每一轮排序的数据交换细节并没给出，我将其留给各位小伙伴作为练习。这里只详细的写了第一轮冒泡排序算法的具体过程，剩余轮数也留给各位小伙伴作为练习。
上图中，在第 3 轮后数字列表已经排好顺序了，在 4 轮不会有数据交换。如果在元素更多的情况下，在排序轮数还没达到 N-1 轮，可能整个数字列表就已经排好顺序了。如果在排序过程中，数字列表已经提前排好顺序，但是算法中没有提前结束排序的功能，那么这个算法就会跑完 N-1 轮排序才会停止。这时，冒泡排序算法的性能并不是很好。
这时，我们可以在算法中包含一个指示器（标志位），如果在一轮排序中没有数据交换，说明整个数字列表已经排好顺序了，那就停止排序，这样可以减少冒泡排序算法的排序轮数，改善冒泡排序算法的性能。
4、C语言描述
#include<stdio.h>//函数声明void BubbleSort(int* arr, int sz);//冒泡排序法(BubbleSort)int main(){//将需要排序的数字存入数组int arr[] = { 5,4,3,2,1};//求数组中元素的个数int sz = (sizeof(arr) / sizeof(arr[0]));//将数组传入函数BubbleSort(arr, sz);//打印已排序的数组for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;}void BubbleSort(int* arr, int sz){//确定冒泡排序的轮数for (int i = 0; i < sz - 1; i++){//标志位,假设在排序过程中剩余的元素已经排好顺序了int flag = 1;//每一次冒泡排序for (int j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = 0;}}//在排序过程中已排好序了,就不会有数据交换//即标志位就不会重新被赋值if (flag == 1){break; //跳出排序轮数循环}}}
关键代码解释：
第二层循环判断条件：j < sz - 1 - i
表达式分两步解释
① sz - 1:在一轮排序中，元素两两比较的次数比元素个数少1。
② -i :减去的是已排序的元素个数，即已排序的元素不参与排序，只排未排序的元素。每一轮排序就会排好一个元素，即排序轮数和已排序元素的个数相同，所以是 -i。
5、Python语言描述
def BubbleSort(arr):'''冒泡排序算法'''# 求数字列表中元素的个数sz = len(arr)for i in range(sz - 1):# 标志位，假设在排序过程中剩余的元素已经排好顺序了flag = 1for j in range(sz - i -1):if arr[j] > arr[j + 1]:arr[j],arr[j + 1] = arr[j + 1],arr[j]flag = 0# 在排序过程中已经排好顺序了，就不会有数据交换# 即标志位就不会重新被赋值if flag == 1:breakif __name__ == '__main__':arr = [5,4,3,2,1]BubbleSort(arr)print("排序后的数字列表")for i in range(len(arr)):print(arr[i],end = " ")
6、Java语言描述
public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {# 标志位，假设在排序过程中剩余的元素已经排好顺序了flag = 1for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 数据交换int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}//在排序过程中已排好序了,就不会有数据交换//即标志位就不会重新被赋值if (flag == 1){break; //跳出排序轮数循环}}}public static void main(String[] args) {int[] arr = {5,4,3,2,1};bubbleSort(arr);System.out.println("排序后的数组：");for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}}
7、总结
这篇文章写了 BubbleSort 算法的文字描述、图示描述和代码描述。在这里为了方便实现此算法只输入了 5 个正整数。算法一般情况下具有通用性，所以这个 BubbleSort 算法可以对 n 个整数进行排序。
各位小伙伴，也可以拷贝代码清单试试输入更多的整数（正整数，0和负整数），看看这个算法能不能对数字列表正确排序。本期的分享总结就到这里了，如果有疑问的小伙伴，我们在评论区交流嗷，笔者必回，我们下期再见啦 ！
如果觉得《【数据结构与算法】冒泡排序算法（BubbleSort）》对你有帮助，请点赞、收藏，并留下你的观点哦！
