1.冒泡排序

1. 冒泡排序算法思想

> [!TIP] 冒泡排序（Bubble Sort）基本思想 > > 经过多次迭代，通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面。

这个过程就像水底的气泡一样从底部向上「冒泡」到水面，这也是冒泡排序法名字的由来。

接下来，我们使用「冒泡」的方式来模拟一下这个过程。

1. 首先将数组想象是一排「泡泡」，元素值的大小与泡泡的大小成正比。
2. 然后从左到右依次比较相邻的两个「泡泡」：
   1. 如果左侧泡泡大于右侧泡泡，则交换两个泡泡的位置。
   2. 如果左侧泡泡小于等于右侧泡泡，则两个泡泡保持不变。
3. 这 1 趟遍历完成之后，最大的泡泡就会放置到所有泡泡的最右侧，就像是「泡泡」从水底向上浮到了水面。

如图所示：

2. 冒泡排序算法步骤

假设数组的元素个数为 n 个，则冒泡排序的算法步骤如下：

1. 第 1 趟「冒泡」：对前 n 个元素执行「冒泡」，从而使第 1 个值最大的元素放置在正确位置上。
   1. 先将序列中第 1 个元素与第 2 个元素进行比较，如果前者大于后者，则两者交换位置，否则不交换。
   2. 然后将第 2 个元素与第 3 个元素比较，如果前者大于后者，则两者交换位置，否则不交换。
   3. 依次类推，直到第 n−1 个元素与第 n 个元素比较（或交换）为止。
   4. 经过第 1 趟排序，使得 n 个元素中第 i 个值最大元素被安置在第 n 个位置上。
2. 第 2 趟「冒泡」：对前 n−1 个元素执行「冒泡」，从而使第 2 个值最大的元素放置在正确位置上。
   1. 先将序列中第 1 个元素与第 2 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换。
   2. 然后将第 2 个元素与第 3 个元素比较，若前者大于后者，则两者交换位置，否则不交换。
   3. 依次类推，直到对 n−2 个元素与第 n−1 个元素比较（或交换）为止。
   4. 经过第 2趟排序，使得数组中第 2 个值最大元素被安置在第 n 个位置上。
3. 依次类推，重复上述「冒泡」过程，直到某一趟排序过程中不出现元素交换位置的动作，则排序结束。

我们以 [5,2,3,6,1,4] 为例，演示一下冒泡排序算法的整个步骤。

冒泡排序算法步骤

3. 冒泡排序代码实现

void bubbleSort(int[] nums) {  
    for(int i = nums.length - 1; i > 0; i--) {  
        for(int j = 0; j < i; j++) {  
            if(nums[j + 1] < nums[j]) { 
	            nums[j], nums[j + 1] =  nums[j + 1], nums[j]
            }
        }  
    }  
}

4. 冒泡排序算法分析

• 最佳时间复杂度：O(n)。最好的情况下（初始时序列已经是升序排列），只需经过 1 趟排序，总共经过 n 次元素之间的比较，并且不移动元素，算法就可以结束排序。因此，冒泡排序算法的最佳时间复杂度为 O(n)。
• 最坏时间复杂度：$O(n^2)$。最差的情况下（初始时序列已经是降序排列，或者最小值元素处在序列的最后），则需要进行 n 趟排序，总共进行$\sum i=2n(i-1)=n(n-1)2$ 次元素之间的比较，因此，冒泡排序算法的最坏时间复杂度为 $O(n^2)$。
• 空间复杂度：O(1)。冒泡排序为原地排序算法，只用到指针变量 i、j 以及标志位 flag 等常数项的变量。
• 冒泡排序适用情况：冒泡排序方法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，冒泡排序方法比较适合于参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况。
• 排序稳定性：由于元素交换是在相邻元素之间进行的，不会改变相等元素的相对顺序，因此，冒泡排序法是一种 稳定排序算法。

5.效率优化

我们发现，如果某轮“冒泡”中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。

经过优化，冒泡排序的最差时间复杂度和平均时间复杂度仍为$O(n^2)$；但当输入数组完全有序时，可达到最佳时间复杂度 O(n) 。

def bubble_sort_with_flag(nums: list[int]):
    """冒泡排序（标志优化）"""
    n = len(nums)
    # 外循环：未排序区间为 [0, i]
    for i in range(n - 1, 0, -1):
        flag = False  # 初始化标志位
        # 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # 交换 nums[j] 与 nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 记录交换元素
        if not flag:
            break  # 此轮“冒泡”未交换任何元素，直接跳出