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

43次阅读

共计 1994 个字符，预计需要花费 5 分钟才能阅读完成。

上面是应用 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}。

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