Java排序之冒泡排序的实现与优化

冒泡排序基本原理

冒泡排序是一种简单的排序算法，其基本思想是通过比较相邻的元素，将较大的数交换到右边，较小的数交换到左边。这样每一轮交换后，未排序的数列中的最大元素就被移动到了最右边，因此被称为“冒泡排序”。

基本算法实现

下面是基本的冒泡排序算法实现：

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

其中，外层循环控制轮数，内层循环控制每轮的比较和交换。每一轮内层循环结束后，未排序的部分的最大值已经被移到了正确的位置。

优化算法实现

虽然冒泡排序是一种简单易懂的算法，但是其时间复杂度为O(n^2)，比较和交换的次数非常多，效率很低。因此，对其进行优化就显得尤为重要。

一、优化循环次数

我们可以在循环内部记录一个标志变量，表示是否进行了交换，如果没有进行交换，说明序列已经有序，直接退出循环，这样可以减少循环次数。

public static void bubbleSort(int[] arr) {
    boolean flag = true;
    for (int i = 0; i < arr.length - 1 && flag; i++) {
        flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
    }
}

二、优化比较次数

我们可以在内层循环中记录最后一次交换的位置，之后的比较都不需要考虑这个位置以后的元素，这样可以减少比较次数。

public static void bubbleSort(int[] arr) {
    int lastSwapIndex = arr.length - 1;
    while (lastSwapIndex > 0) {
        int k = lastSwapIndex;
        lastSwapIndex = 0;
        for (int j = 0; j < k; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                lastSwapIndex = j;
            }
        }
    }
}

示例说明

以下是针对两个不同数据集合的测试用例：

示例一

对于输入数组{10, 7, 3, 1, 9, 7, 4}，经过冒泡排序算法之后，得到的结果为{1, 3, 4, 7, 7, 9, 10}。过程如下：

第1轮：
7 10 3 1 9 7 4
7 3 10 1 9 7 4
7 3 1 10 9 7 4
7 3 1 9 10 7 4
7 3 1 9 7 10 4
7 3 1 9 7 4 10
第2轮：
3 7 1 9 7 4 10
3 1 7 9 7 4 10
3 1 7 7 9 4 10
3 1 7 7 4 9 10
第3轮：
1 3 7 4 7 9 10
1 3 4 7 7 9 10
第4轮：
1 3 4 7 7 9 10
第5轮：
1 3 4 7 7 9 10
第6轮：
1 3 4 7 7 9 10

示例二

对于输入数组{1, 2, 3, 4, 5, 6}，经过冒泡排序算法之后，得到的结果为{1, 2, 3, 4, 5, 6}。由于该数组已经有序，优化后的冒泡排序算法只执行了一轮循环，效率大大提高。

总结

冒泡排序虽然算法简单易懂，但是效率较低，应该尽量避免在实际的应用场景中使用，针对其时间复杂度比较高的问题，我们可以进行相应的优化，例如减少比较次数和循环次数等。