排序-冒泡排序（bubble sort）

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，就如同水底的气泡一样逐渐向上冒。

冒泡排序的特点包括：

1. 时间复杂度：

   • 最好情况（输入数组已经是排序好的）：O(n)，因为此时只需遍历一次数组即可发现没有交换发生，说明数组已经是有序的。
   • 平均情况和最坏情况（数组完全逆序或随机排列）：O(n^2)，因为需要进行多次遍历来确保所有元素都达到其最终位置。

2. 空间复杂度：

   • O(1)，冒泡排序也是原地排序算法，除了交换元素时使用的临时变量外，不需要额外的存储空间。

3. 稳定性：

   • 冒泡排序是稳定的排序算法。如果存在相等的元素，它们的相对顺序在排序前后不会改变。

4. 算法步骤：

   • 从数组的第一个元素开始，比较相邻的两个元素，如果前一个比后一个大，则交换它们的位置。
   • 对每一对相邻元素做同样的比较，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
   • 针对所有的元素重复以上的步骤，除了最后一个。
   • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

尽管冒泡排序实现简单，但由于其较低的效率，在处理大规模数据集时并不常用。在实践中，通常会采用更高效的排序算法，如快速排序、归并排序等。不过，冒泡排序在小规模数据或几乎已排序的数据集中仍然有其简单直接的应用价值。此外，通过添加标志位来检测在一次遍历中是否有发生交换，可以提前结束没有交换的循环，从而优化冒泡排序的最坏情况性能。

一下是冒泡排序的Java代码实现：

/* 冒泡排序 */
void bubbleSort(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; 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;
            }
        }
    }
}

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

/* 冒泡排序（标志优化） */
void bubbleSortWithFlag(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // 初始化标志位
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; 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;
                flag = true; // 记录交换元素
            }
        }
        if (!flag)
            break; // 此轮“冒泡”未交换任何元素，直接跳出
    }
}

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

一下是冒泡排序的实现图