冒泡排序

什么是冒泡排序

冒泡排序是算法学习的入门课程，也是一种基础的排序算法。它的命名借鉴了生活中的一个现象，即水底的气泡会逐渐向上漂浮，并且越到水面的气泡会变得越大。

冒泡排序简单描述是：每经过一次遍历，列表中最大的元素“冒泡”到列表中正确的位置。

冒泡排序的价值

冒泡排序是一种逻辑简单容易理解的排序算法，一般最为学算法的入门。
冒泡是只有当两个元素不满足条件的时候才会交换，只有后一个大于前一个才会交换，所以是一种稳定的排序算法。
这种固定的比较方式决定了冒泡排序的弊端，对于每个数组都会进行从头到尾的依次遍历，不论这个数组是否有序，所以在对大型数据排序时，冒泡排序的效率是非常低的。

冒泡排序的实现思路

比较相邻的两个元素。如果第一个比第二个大，就交换它们的位置。
对每一对相邻的元素做同样的操作，从开始的第一对到结尾的最后一对。这一步结束后，最后的元素应该是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
重复步骤 1~3，直到排序完成。

具体实现

第一轮排序，此时元素都处于待排序状态，依次遍历相邻元素，并对顺序不正确的元素交换位置。经过第一轮排序后，最大的元素“冒泡”到数组的最后，即数组中最大的元素经过比较交换到了正确的位置。
```
# 对比的实现逻辑
for j in range(n - 1):
    print(f"===第{j}轮比较排序===")
    if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
```

重复 n 个轮次，以完成其他元素的排序。

 for i in range(n):
    print(f"第{i}轮遍历")
    for j in range(n - 1):
        print(f"===第{j}轮比较排序===")
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]

不难看出上述代码并不能实现冒泡排序，因为每次的内层比较都是比较了全数组，而冒泡的实现是，经过一轮排序都可“归位”一个元素，也就是下轮排序无需再比较该元素，所以比较的 for 循环范围应该缩减。
```
for j in range(n -i- 1):
```

在最后一次排序时，待排序序列只剩一个元素，也就是原始数组中最小的元素，这时不需要再进行比较，数组已完成排序过程。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        print(f"第{i}轮遍历")
        for j in range(n -i- 1):
            print(f"===第{j}轮比较排序===")
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

完整代码（Python）

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        print(f"第{i}轮遍历")
        for j in range(n - i - 1):
            print(f"===第{j}轮比较排序===")
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def test_bubble_sort():
    assert bubble_sort([7, 6, 5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5, 6, 7]

完整代码（Java）

public class Sort {
    public int[] bubbleSort(int[] list) {
        // 一共比几轮
        for (int j = 0; j < list.length - 1; j++) {
            System.out.println("现在比到了第"+j+"轮");
            for (int i = 0; i < list.length-j - 1; i++) {
                System.out.println("对比交换了第几"+i+"次");
                // 如果前一位大于后一位
                if (list[i] > list[i + 1]) {
                    int temp = list[i];
                    list[i] = list[i + 1];
                    list[i + 1] = temp;
                }
            }
        }
        return list;
    }
}

package com.ceshiren.search;

import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.*;

class SortTest {

    @Test
    void bubbleSort() {
        Sort sort = new Sort();
        int [] list = {5,1,3,6,2};
        sort.bubbleSort(list);
        int [] sortedList = {1,2,3,5,6};
        assertEquals(Arrays.toString(sortedList), Arrays.toString(list));
    }
}

冒泡排序的复杂度分析

时间复杂度

# n轮，其时间复杂度为O(n)
for i in range(n):
        # 交换n次，其时间复杂度为O(n)
    for j in range(n -i- 1):
# 嵌套循环直接相乘，O(n)*O(n)

交换次数虽然逐级递减，但是仍可以将其视为 n 次，其时间复杂度为 O(n)。
在整个冒泡的过程中，需要对比 n 轮，其时间复杂度为 O(n)。
所以整体时间复杂度为 O(n)*O(n) = O(n^2^)。

空间复杂度

冒泡排序只定义了一个参数的变量，所以空间复杂度为 O(1)。