冒泡排序算法（BubbleSort）

1、BubbleSort算法描述

假设将需要排序的数字列表分成两个子列表:已排序的和未排序的。在未排序子列表中，最小的元素通过冒泡的方法选出来并移到已排序子列表中。

未排序子列表中的元素从前往后两两比较，如果一个元素比另外一个元素小，那么将这两个元素交换位置；否则，不进行任何处理，则进行下一次的元素两两比较；直到最大的元素排到合适的位置。最大元素排到合适的位置称之为一轮排序，一个含有N个元素的数字列表则需要N-1轮来完成数据排序。

为什么是N-1轮排序？当未排序子列表剩下两个元素时，只需要交换一次数据，就完成了整个原始列表的数据排序。所以排序轮数比元素的个数少1。

2、用图示描述BubbleSort算法

注：红色方块左边为未排序元素，右边为已排序元素

第一轮，从9开始并把它与5比较，9大于5则这两个元素进行位置交换。9大于7则这两个元素进行位置交换。9大于1则这两个元素进行位置交换。9大于3则这两个元素进行位置交换，9到达合适的位置。图中只给出了每一轮排序后的数字列表，每一轮排序的数据交换细节并没给出，我将其留给各位看官作为练习。这里只详细的写了第一轮冒泡排序算法的具体过程，剩余轮数也留给各位看官作为练习。

上图中，在第3轮后数字列表已经排好顺序了，在4轮不会有数据交换。如果在元素更多的情况下，在排序轮数还没达到N-1轮，可能整个数字列表就已经排好顺序了。如果在排序过程中，数字列表已经提前排好顺序，但是算法中没有提前结束排序的功能，那么这个算法就会跑完N-1轮排序才会停止。这时，冒泡排序算法的性能并不是很好。

这时，我们可以在算法中包含一个指示器（标志位），如果在一轮排序中没有数据交换，说明整个数字列表已经排好顺序了，那就停止排序，这样可以减少冒泡排序算法的排序轮数，改善冒泡排序算法的性能。

这个算法就是因其中数字（例如第一轮排序的数字9）从列表的开始向顶部移动的方式就像水泡从水中冒出的样子而得名。

3、用代码描述BubbleSort算法

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>//函数声明void BubbleSort(int* arr, int sz);//冒泡排序法(BubbleSort)int main(){//将需要排序的数字存入数组int arr[] = { 7,5,9,1,3 };//求数组中元素的个数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。

4、总结

这篇文章写了BubbleSort算法的文字描述、图示描述和代码描述。在这里为了方便实现此算法只输入了5个正整数。算法一般情况下具有通用性，所以这个BubbleSort算法可以对n个整数进行排序。各位看官，也可以拷贝代码试试输入更多的整数（正整数，0和负整数），看看这个算法能不能对数字列表正确排序。今天的分享总结就到这里了，我们下期再见 ！！！