冒泡排序

冒泡排序（Bubble Sort）

工作原理

冒泡排序通过不断地交换相邻的未按顺序排列的元素，使较大的元素逐渐向数组的末尾“冒泡”，从而实现排序。

1. 比较相邻的元素：如果第一个比第二个大（升序排序），则交换它们的位置。
2. 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对。这样，最后的元素应该是最大的数。
3. 重复步骤1-2，直到整个数组排序完成。

Java实现

public class BubbleSort {

    /**
     * 冒泡排序算法
     * @param arr 要排序的数组
     */
    public static void sort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        // 遍历所有元素
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // 最后的i个元素已经在正确的位置，无需检查
            for (int j = 0; j < n - 1 - i; j++) {
                // 如果当前元素大于下一个元素，则交换它们
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            
            // 如果在某次遍历中没有发生交换，说明数组已经有序
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 交换数组中的两个元素
     * @param arr 数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 打印数组中的元素
     * @param arr 数组
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    /**
     * 主函数
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        int[] sampleArray = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Original array:");
        printArray(sampleArray);

        sort(sampleArray);

        System.out.println("Sorted array:");
        printArray(sampleArray);
    }
}

代码解析

1. sort() 方法：这是冒泡排序的核心实现。它接受一个整型数组作为参数，并对其进行排序。
2. 外层循环：用于控制遍历次数，每次遍历都会将未排序部分的最大值放置在正确的位置。
3. 内层循环：负责每次遍历的实际操作，比较并可能交换相邻元素。
4. swap() 方法：用于交换数组中的两个元素。
5. printArray() 方法：用于打印数组中的元素。
6. main() 方法：测试排序功能的方法。

注意事项

• 时间复杂度：冒泡排序的平均和最坏情况下的时间复杂度均为 O(n^2)，其中 n 是数组长度。但是，在最好的情况下（即输入数组已经是排序好的），时间复杂度为 O(n)，因为内层循环不会执行。
• 稳定性：冒泡排序是稳定的排序算法，因为它不会改变相等元素之间的原有顺序。
• 空间复杂度：冒泡排序的空间复杂度为 O(1)，因为它只需要一个额外的存储空间来保存当前要交换的元素。

适用场景

冒泡排序适合于小规模数据的排序，或者当输入数据部分已排序时。由于其时间复杂度较高，不推荐用于大规模数据集的排序。

希望这段代码及其说明能够帮助您更好地理解和实现冒泡排序算法。如果您有任何疑问或需要进一步的帮助，请随时告诉我。