关于计算机:为什么冒泡排序是稳定的

上面是应用 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 是待排序数组的长度。只管冒泡排序不是最高效的排序算法，但因为其简略性和稳定性，它在某些特定状况下依然是一个实用的抉择。