冒泡排序

冒泡排序是一种最简单的排序算法。顾名思义，就是每次排序之后，最大的元素会像气泡浮出水面一样移动到最后的位置，每一次循环都能确定一个序列中的最大元素。

算法思想：

1. 比较相邻的两个元素，如果第一个比第二个大，就交换
2. 对每一对相邻的两个元素执行同样的操作，从开始执行到最后，这一步做完之后，最后的元素将是最大的元素
3. 对前面n-1个元素执行1，2两步
4. 重复执行前面步骤，直到没有一对元素需要比较交换

算法代码

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