冒泡排序是一种最简单的排序算法。顾名思义，就是每次排序之后，最大的元素会像气泡浮出水面一样移动到最后的位置，每一次循环都能确定一个序列中的最大元素。
算法思想：
- 比较相邻的两个元素，如果第一个比第二个大，就交换
- 对每一对相邻的两个元素执行同样的操作，从开始执行到最后，这一步做完之后，最后的元素将是最大的元素
- 对前面n-1个元素执行1，2两步
- 重复执行前面步骤，直到没有一对元素需要比较交换
算法代码
void bubbleSort(int array[], int length)
{
int i, j, tmp;
if (1 >= length)
return;
for (i = length-1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (array[j] > array[j+1]) {
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
算法分析
- 最好情况下，即一开始就是有序的，那么就不用执行交换操作了，只需要执行1+2+3+…+n次比较，时间花销为n(n-1)/2，因此，最优复杂度为O(n^2)
- 最差情况下，也就是开始逆序，那么每一次排序都要比较和交换两个元素，时间花销为3n(n-1)/2，因此，最差时间复杂度为O(n^2)，相比于上面的最优情况，就是多了上面代码中的交换操作。
- 平均情况下，时间复杂度为O(n^2)。
- 空间复杂度为交换过程中申请的额外空间，显然，我们只需要一个变量，因此复杂度为O(1)。
- 很多地方认为冒泡排序的最优复杂度为O(n)，这是另一种优化方法，就是引入一个标志位，用于判断是否已经有序了，当第一趟遍历，全部元素无需交换，那么标志位置位，无需后续的操作，排序结束，只进行了一趟遍历，因此为O(n)。
- 有些地方认为最好的空间复杂度为O(0)，因为交换无需引入变量，当然这也是可行的，但是最好不要这样做，因为这样容易复杂化程序的理解。
过程展示
bubble-sort.gif
