冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，其基本思想是通过重复遍历要排序的列表，比较每对相邻的元素，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复进行的，直到没有再需要交换的元素为止，也就是说该列表已经排序完成。

尽管冒泡排序的实现简单，但它的时间复杂度较高，不适合处理大规模数据集。然而，冒泡排序对于教学和理解排序算法的基本概念非常有帮助。

基本思想

冒泡排序的核心思想是通过多次遍历来逐个“冒泡”出最大（或最小）的元素到正确的位置。每次遍历都会将当前未排序部分的最大（或最小）元素移动到其正确的位置。这个过程重复进行，直到整个列表完全排序。

代码实现

查看代码

java

public class BubbleSort {

    // 冒泡排序方法
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // 遍历未排序的部分
            for (int j = 0; j < n - 1 - 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) {
                break;
            }
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("原始数组:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }
}

步骤

初始化：设定一个标志位 swapped，用于标记是否发生了交换。
遍历数组：从第一个元素到最后一个元素，比较每一对相邻的元素。
交换元素：如果当前元素大于（或小于）它的下一个元素，则交换它们的位置。
重复遍历：重复步骤 2 和 3 直到整个数组排序完成，或者在某次遍历中没有发生任何交换（此时数组已经排序完成）。

代码解释

bubbleSort 方法：这是冒泡排序的核心方法。它通过外层循环控制遍历的轮数，内层循环用于比较并交换相邻元素。每次内层循环结束后，最大的元素会被移动到正确的位置。
打印数组的方法：printArray 方法用于打印数组，方便查看排序结果。
main 方法：测试冒泡排序的主程序入口。

时间复杂度

最好情况： $O (n)$ ，当输入数组已经是有序的情况下，第一轮遍历后就不会再发生交换，因此只需要遍历一次即可。
平均情况： $O (n^{2})$ ，在平均情况下，每次遍历都需要比较和交换大量的元素。
最坏情况： $O (n^{2})$ ，当输入数组是逆序的情况下，每次遍历都需要比较和交换所有的元素。

空间复杂度

冒泡排序的空间复杂度为 $O (1)$ ，因为它只需要几个额外的变量来保存临时交换的数据，不需要额外的存储空间。

优化技巧

虽然冒泡排序的时间复杂度较高，但可以通过一些技巧来优化其性能：

提前终止：如果在某轮遍历中没有发生任何交换，说明数组已经排序完成，可以提前终止排序。
记录最后一个交换的位置：在每轮遍历中记录最后一次交换的位置，下一轮遍历只需要遍历到该位置即可，因为之后的元素已经是有序的。

冒泡排序 ​

基本思想 ​

代码实现 ​

步骤 ​

代码解释 ​

时间复杂度 ​

空间复杂度 ​

优化技巧 ​