冒泡排序 ​

冒泡排序是最基础的排序算法，由于其直观性，经常作为首个介绍的排序算法。其原理为：

• 内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。
• 外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。

如下图所示，首轮「内循环」后，数组最大元素已被交换至数组最右边；接下来，只需要完成数组剩余 $N - 1$ 个元素的排序即可（设数组元素数量为 $N$ ）。同理，对剩余 $N - 1$ 个元素执行「内循环」，可将第二大元素交换至剩余数组最右端，以此类推……

<,,,,,,,,,>

如下图所示，冒泡排序的「外循环」共 $N - 1$ 轮，每轮「内循环」都将当前最大元素交换至数组最右边，从而完成对整个数组的排序。

如下图所示，为示例数组 nums = [4, 1, 3, 1, 5, 2] 的冒泡排序算法运行过程。

<,,,,,,,,,,,,,,,,,,,,,,,,,,,,>

代码 ​

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):           # 外循环
        for j in range(N - i - 1):   # 内循环
            if nums[j] > nums[j + 1]:
                # 交换 nums[j], nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

void bubbleSort(int[] nums) {
    int N = nums.length;
    for (int i = 0; i < N - 1; i++) {          // 外循环
        for (int j = 0; j < N - i - 1; j++) {  // 内循环
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j], nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
    }
}

void bubbleSort(vector<int> &nums) {
    int N = nums.size();
    for (int i = 0; i < N - 1; i++) {          // 外循环
        for (int j = 0; j < N - i - 1; j++) {  // 内循环
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j], nums[j + 1]
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}

算法特性 ​

• 时间复杂度 $O(N^2)$ ：
  • 最佳 $\Omega(N)$ ： 普通冒泡排序的时间复杂度恒为 $O(N^2)$ ，对于近似排序数组，通过加入标志位可实现提前返回（详情请见下文）。
  • 平均与最差 $O(N^2)$ ：「外循环」共 $N - 1$ 轮，使用 $O(N)$ 时间；每轮「内循环」分别遍历 $N - 1$ , $N - 2$ , $\cdots$ , $2$ , $1$ 次，平均 $\frac{N}{2}$ 次，使用 $O(\frac{N}{2}) = O(N)$ 时间；因此，总体时间复杂度为 $O(N^2)$ 。
• 空间复杂度 $O(1)$ ： 只需原地交换元素，使用常数大小的额外空间。
• 冒泡排序是通过不断 交换元素 实现排序（交换 2 个元素需要 3 次赋值操作），因此速度较慢；
• 原地： 指针变量仅使用常数大小额外空间，空间复杂度为 $O(1)$ ；
• 稳定： 元素值相同时不交换，因此不会改变相同元素的相对位置；
• 自适应： 通过增加一个标志位 flag ，若某轮内循环未执行任何交换操作时，说明已经完成排序，因此直接返回。此优化使冒泡排序的最优时间复杂度达到 $O(N)$（当输入数组已排序时）；

标志位优化 ​

普通冒泡排序的时间复杂度恒为 $O(N^2)$​ ，与输入数组的元素分布无关。

通过增加一个标志位 flag ，若在某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。

优化后的冒泡排序的最差和平均时间复杂度仍为 $O(N^2)$ ；在输入数组 已排序 时，达到 最佳时间复杂度 $\Omega(N)$ 。

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):
        flag = False         #  初始化标志位
        for j in range(N - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 记录交换元素
        if not flag: break   # 内循环未交换任何元素，则跳出

void bubbleSort(int[] nums) {
    int N = nums.length;
    for (int i = 0; i < N - 1; i++) {
        boolean flag = false; // 初始化标志位
        for (int j = 0; j < N - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true;  // 记录交换元素
            }
        }
        if (!flag) break;     // 内循环未交换任何元素，则跳出
    }
}

void bubbleSort(vector<int> &nums) {
    int N = nums.size();
    for (int i = 0; i < N - 1; i++) {
        bool flag = false;   // 初始化标志位
        for (int j = 0; j < N - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = true; // 记录交换元素
            }
        }
        if (!flag) break;    // 内循环未交换任何元素，则跳出
    }
}