为什么冒泡排序是稳定的?

下面是使用Java实现冒泡排序的源代码，每一行都有详细的注释来解释代码的功能和处理边界情况。我还会在后面解释为什么冒泡排序是稳定的。

public class BubbleSort {
    
    // 冒泡排序方法
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        
        // 遍历数组元素
        for (int i = 0; i < n - 1; i++) {
            
            // 标记是否有交换操作
            boolean swapped = false;
            
            // 每次遍历将最大的元素移动到最后
            for (int j = 0; j < n - i - 1; j++) {
                
                // 如果前面的元素比后面的元素大，则进行交换
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            
            // 如果在一次遍历中没有进行交换操作，说明数组已经有序，可以提前结束排序
            if (!swapped) {
                break;
            }
        }
    }
    
    // 交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 打印数组元素
    private static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        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);
    }
}

以上代码实现了冒泡排序算法，现在让我们逐行解释代码的功能和处理边界情况。

public class BubbleSort {
    
    // 冒泡排序方法
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        
        // 遍历数组元素
        for (int i = 0; i < n - 1; i++) {
            
            // 标记是否有交换操作
            boolean swapped = false;
            
            // 每次遍历将最大的元素移动到最后
            for (int j = 0; j < n - i - 1; j++) {
                
                // 如果前面的元素比后面的元素大，则进行交换
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            
            // 如果在一次遍历中没有进行交换操作，说明数组已经有序，可以提前结束排序
            if (!swapped) {
                break;
            }
        }
    }
    
    // 交换数组中的两个元素
    private static

 void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // 打印数组元素
    private static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        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);
    }
}

现在，让我们解释为什么冒泡排序是稳定的。

冒泡排序算法是通过比较相邻的元素并交换它们的位置来排序数组的算法。在每次遍历中，将最大的元素冒泡到最后的位置。由于每次比较的是相邻元素，所以对于相同的元素，它们之间的相对顺序不会改变。

考虑以下情况：

假设有一个数组 arr = {5, 2, 8, 2, 5}，其中有两个相同的元素 2 和 5。

首先，第一个遍历将最大的元素 8 冒泡到最后，数组变为 {2, 5, 2, 5, 8}。

在第二次遍历中，比较和交换的过程如下：

• 比较 arr[0] 和 arr[1]，不需要交换。
• 比较 arr[1] 和 arr[2]，不需要交换。
• 比较 arr[2] 和 arr[3]，需要交换，数组变为 {2, 2, 5, 5, 8}。

最后一次遍历时，不需要进行任何交换操作，数组保持不变。

所以，无论相同元素的相对顺序如何，冒泡排序都会保持它们的相对顺序不变。这就是为什么冒泡排序是稳定的。

冒泡排序的时间复杂度为O(n^2)，其中n是待排序数组的长度。尽管冒泡排序不是最高效的排序算法，但由于其简单性和稳定性，它在某些特定情况下仍然是一个实用的选择。