重温经典排序算法--气泡排序 - 插图 + C/C++ 实现

1.冒泡排序算法原理：

【说明】这里实现的冒泡排序算法均为从小到大排序
1.比较相邻的元素，如果第一个比第二个大，就交换他们；
2.第一趟排序：第一个和第二个比较，若前者比后者大则交换；第二个和第三个比较满足前者较大则交换；随后依次进行相邻两个数的比较与交换，直到最后一对。第一趟排序结束后，最大的数将会出现在最后一位；
3.第二趟排序：与2相同的步骤进行比较与交换。第二趟排序结束后，第二大的数将会出现在倒数第二位；
【注意】此时第一趟排序之后产生的最大的数不应该参与本趟排序，即已经排好序的数不可参与后续的排序
4.以此类推，之后每趟排序次数依次减少，直到没有任何一对数字需要比较。

2.算法性能分析：

（1）时间复杂度

a.最好状态的时间复杂度：如果初始状态为完全正序，则扫描一趟即可完成排序，此时比较次数C为n-1，移动次数M为0，即$$C=n-1$$$$M=0$$最好状态时间复杂度为$$O(n)$$
b.最坏状态的时间复杂度：如果初始状态为完全反序，则需要进行n-1趟排序，每趟排序要进行n-1次比较，每次比较都需要移动三次，则$$C_{max}=\frac{n(n-1)}{2}=O(n^2)$$$$M_{max}=\frac{3n(n-1)}{2}=O(n^2)$$最坏状态时间复杂度为$$O(n^2)$$

综上，冒泡排序平均时间复杂度为$$O(n^2)$$

（2）算法稳定性

冒泡排序实质就是把大（小）的元素往后（前）调整，比较相邻的元素，满足前者大于后者则交换，因此，若两元素相等也是不会进行交换的，所以，冒泡排序是一种稳定的排序算法。

3.图解分析

要排序的数组：[8,7,6,5,3]: