冒泡排序
接下来我们要介绍的是排序算法中极为标志性，并且经常在教材中作为经典案例出现的——冒泡排序。
算法思想
冒泡排序(Bubble sort)的算法思想也是较为容易去理解的，我们参照冒泡这一物理现象，会发现，往往大的气泡都会往上运动，而小的气泡往往都在下方。冒泡排序的名字也就是这么由来的。它的算法步骤大致如下：
- 从数组的开头开始，将第一个数据与第二个数据进行比较，按照指定的比较思想（大的放前面or小的放前面）完成交换操作
- 再将此时的第二个数据与第三个数据再次进行步骤1中的操作，以此类推，直到比较完最后两个数据
- 此时的数组如果不是完全有序，那么从头开始进行步骤1和步骤2的操作，直到完全有序。
图解
C语言代码分析
代码语言：javascript复制void BubbleSort(int* a, int n)
{
bool exchange = false;//标记是否发生交换
for(int j=0;j<n;j )
{
for (int i = 1; i < n-j; i )
{
//如果前一个元素大于后一个元素，交换
if (a[i - 1] > a[i])
{
int temp = a[i - 1];
a[i - 1] = a[i];
a[i] = temp;
}
if(exchange == false)//如果没有发生交换，说明此时已经有序，那么就直接跳出
{
break;
}
}
}
}时间复杂度
我们可以看出，实际上冒泡排序是华而不实的一种排序算法。它在数据较少或者较为有序的时候，可以有很好的效率，但是一旦数据多起来或者较为无序，那么需要重复的次数就会大幅度增加，从而后期乏力，效率降低。
- 在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为O(n)。
- 在最坏情况下，冒泡排序要执行**(n-1)n/2次交换操作，时间复杂度为O(n2)**。
- 冒泡排序的平均时间复杂度为O(n2)。
稳定性
鉴于冒泡排序不会改变前后元素的相对位置，所以：稳定
