冒泡排序 | 是熊是猫溜溜

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误>就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”>到数列的顶端。

主要思想

依次比较两个相邻的元素，如果它们顺序错误，则交换，最终大数会沉向尾部。重复上面的步骤知道数组有序，下面以正序为例进行详细说明整个过程。

原数据：

1	[9] [8] [7] [1] [3] [5]

第一步：比较[9]和[8]，由于[9]大于[8]，按照正序逻辑[9]在后面，因此需要交换它们的位置，得到新的数组如下所示。

1	[8] [9] [7] [1] [3] [5]

第二步：比较比较[9]和[7]，同理需要交换它们的位置，得到新的数组如下所示。

1	[8] [7] [9] [1] [3] [5]

依次比较原理同上，直到最后一组元素相邻元素比较之后，我们可以得到第一轮冒泡之后的结果，如下所示，可以很明显看到元素[9]最终沉到了尾部，因为它是正序里面最大的结果。

1	[8] [7] [1] [3] [5] [9]

同理我们进行第二轮冒泡，会将[8]沉到元素尾部，得到如下结果，这里需要注意，由于第一轮冒泡，已经把最大的元素[9]放到了最后一个位置，第二轮冒泡则无需和[9]进行比较，就可以把[8]放到倒数第二的位置。

1	[7] [1] [3] [5] [8] [9]

最终在经过了n-1轮冒泡之后（n为元素个数），我们可以最终得到一个有序的数组。

1	[1] [3] [5] [7] [8] [9]

时间与空间复杂度

冒泡排序是稳定的排序算法，其时间复杂度计算公式如下。可以看到冒泡排序，最好的情况与最坏的情况下，时间复杂度均为2^n，空间复杂度为1，平均时间复杂度为2^n。

$$
(n-1) + (n-2) + (n-3) + … + 1 = ((n-1) + 1) * (n-1) / 2 = \frac{n * (n-1)}{2}
$$

代码实现

less函数与exch函数参见文章排序算法序言。

public static void bubble(Comparable[] c){
    int N = c.length;
    for(int i = 0; i < N-1; i++){
        for(int j = 0; j < N-i-1; j++){
            if(less(c[j+1], c[j])){
                exch(c, j, j+1);
            }
        }
    }
}