排序算法：冒泡排序

冒泡排序的原理很简单，以升序为例，假设数组有n个元素，就是从第0个元素开始遍历，逐步比较arr[0]和arr[1]，arr[1]和arr[2]，arr[2]和arr[3]……arr[n-2]和arr[n-1]，如果发现左边的元素大于右边的元素，那么就交换位置，所以arr[n-1]就会是整个数组里最大的元素。

然后重新从arr[0]开始比较，一直比较到arr[i-1]（i是当前未排序部分的末尾索引），拿出第二大的元素放在倒数第二个位置（不需要手动放，在比较的过程中它会自动跑到那个位置），然后从0到n-2，从0到n-3……直到从0-1，当最后两个元素比较结束，整个数组就排序成功了，所以i就是从数组长度n-1递减到1。

所以实现冒泡排序的关键在于，每一轮循环都将当前最大的元素“冒泡”到未排序区的最后，想象成先冒了最大的那个泡，然后在剩下的元素里再冒最大的泡排到上一个最大泡的后面。

实现

Java实现

/**
 * 冒泡排序
 */
public static void bubbleSort(int[] arr) {
    // 从最后一个位置开始
    for (int i = arr.length - 1; i > 0; i--) {
        // 从0开始比较相邻元素，比较到i就行，因为i后面的都是比较过的元素
        for (int j = 0; j < i; j++) {
            // 如果碰到左边的大，那就把它放右边，所以循环结束的时候最大的元素就会放最右边了
            if (arr[j] > arr[j + 1]) {
                // 交换元素的值
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

以上就是标准的冒泡排序。

但是如果某一次循环发现没有交换过元素，说明元素已经有序了，这时候就没必要再比下去了，可以提前结束循环，算是一个优化的点。

优化

/**
 * 冒泡排序
 */
public static void bubbleSort(int[] arr) {
    // 从最后一个位置开始
    for (int i = arr.length - 1; i > 0; i--) {
        // 记录本次循环是否交换过元素
        boolean swapped = false;
        // 从0开始比较相邻元素，比较到i就行，因为i后面的都是比较过的元素
        for (int j = 0; j < i; j++) {
            // 如果碰到左边的大，那就把它放右边，所以循环结束的时候最大的元素就会放最右边了
            if (arr[j] > arr[j + 1]) {
                // 交换元素的值
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 交换了元素，记录下来
                swapped = true;
            }
        }
        // 如果没有交换元素，说明数组已经有序，退出循环结束排序
        if (!swapped) {
            return;
        }
    }
}

很明显，时间复杂度在最好的情况下，也就是arr比较之前已经有序了，这时候需要遍历内层循环就通过swapped直接结束了，时间复杂度为O(n)，最差的情况呢就是每次都需要遍历，提前退出的机会都没有，所以就是需要比较n+(n-1) + (n-2)……+2+1=(1+n)×n/2，等差数列相加，就是上底加下底乘高除以2即可，结果的最大幂次是n²，所以时间复杂度是O(n²)，平均复杂度也还是O(n²)。如果是没优化前的实现方式，那哪怕原本也排序好了也还是要比较(1+n)×n/2次，时间复杂度是O(n²)，因此O(n)是优化版冒泡排序的最好时间复杂度。至于空间复杂度，由于这是原地排序，所以空间复杂度为O(1)。

稳定性的话，当比较到两个相等元素的时候，不会交换位置，所以冒泡排序是稳定的。

总结

时间复杂度（最好）：O(n)

时间复杂度（最差）：O(n²)

时间复杂度（平均）：O(n²)

空间复杂度：O(1)

稳定性：稳定