排序算法图解之Java冒泡排序及优化

我来为你详细讲解“排序算法图解之Java冒泡排序及优化”的完整攻略。

简介

排序算法在计算机学科中是非常重要的内容，冒泡排序就是其中的一种，设计简单，易于理解和实现，其时间复杂度为O(n^2)。本篇文章主要介绍了Java语言实现冒泡排序的方式以及针对普通冒泡排序算法的优化。

冒泡排序

冒泡排序是稳定排序中的一种，其基本操作是将相邻的元素进行比较和交换，每次循环可以保证一个元素就位。具体操作如下：

从列表的第一个元素开始，依次比较相邻的两个元素，如果第一个元素大于第二个元素，则交换这两个元素；
继续逐个比较相邻的元素，直到遍历到列表的倒数第二个元素；
上述操作会使得列表的最大元素位于列表的末尾；
重复上述过程，直到整个列表有序。

下面是Java代码实现冒泡排序：

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

其中，arr表示待排序的列表，n表示列表的长度。

冒泡排序的优化

虽然冒泡排序是一种简单直观的排序算法，但其时间复杂度为O(n^2)，在处理大规模数据时效率并不高。下面是两种常见的冒泡排序优化方法：

优化一：添加标记位

当列表已经有序时，冒泡排序仍然会执行完所有的比较和交换操作，此时可以通过添加标记位来优化算法时间复杂度，具体操作如下：

初始化标记位为false；
从列表的第一个元素开始，依次比较相邻的两个元素，如果第一个元素大于第二个元素，则交换这两个元素，并将标记位置为true；
如果当前循环中没有发生交换操作，则列表已经有序，直接退出循环；
重复上述操作，直到整个列表有序。

下面是Java代码实现冒泡排序优化：

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

优化二：记录最后一次交换位置

在一次循环过程中，如果发现有多组元素需要交换，那么应该让最小的元素尽可能地往前调整，这样可以避免每次循环交换多组元素时总是将最小元素调到列表的末尾。具体操作如下：

初始化最后一次交换位置为列表的尾部位置n；
从列表的第一个元素开始，依次比较相邻的两个元素，如果第一个元素大于第二个元素，则交换这两个元素，并更新最后一次交换位置；
如果当前循环中没有发生交换操作，则列表已经有序，直接退出循环；
将最后一次交换位置更新为当前循环中进行交换操作的最后一组交换位置；
重复上述操作，直到整个列表有序。

下面是Java代码实现冒泡排序优化：

public static void bubbleSortOptimize2(int[] arr) {
    int n = arr.length;
    int lastExchangeIndex = n;
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        int temp = lastExchangeIndex;
        for (int j = 0; j < temp - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
                flag = true;
                lastExchangeIndex = j + 1;
            }
        }
        if (!flag) {
            break;
        }
    }
}

示例说明

示例一

假设待排序的列表为[2, 3, 1, 5, 4]，那么经过一个循环之后，列表变成了[2, 1, 3, 4, 5]，这里只展示了第一个最大元素2的位置，下一个循环会将第二大元素5调整到列表的倒数第二个位置。这个过程称为一次冒泡过程，该列表的冒泡过程需要进行4次，才能得到有序的列表。具体示例如下：

待排序列表	第一次冒泡过程	第二次冒泡过程	第三次冒泡过程	第四次冒泡过程
[2, 3, 1, 5, 4]	[2, 1, 3, 4, 5]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]

可以看到，在第一次冒泡过程中，列表的第一个元素2被调整到了倒数第二个位置，而元素5并没有发生交换。这就说明，在元素2被调整到了列表的倒数第二个位置之后，列表的后半部分已经有序了，所以在后面的冒泡过程中就不需要再次比较和交换后半部分的元素。

示例二

假设待排序的列表为[5, 2, 4, 6, 1, 3]，那么经过优化一之后的冒泡排序，只需要进行三次冒泡过程就可以得到有序列表[1, 2, 3, 4, 5, 6]。在第三次冒泡过程中，列表元素[4, 5, 6]已经有序，所以在后面的冒泡过程中就不需要再比较和交换这几个元素。具体示例如下：

待排序列表	第一次冒泡过程	第二次冒泡过程	第三次冒泡过程
[5, 2, 4, 6, 1, 3]	[2, 4, 5, 1, 3, 6]	[2, 4, 1, 3, 5, 6]	[2, 1, 3, 4, 5, 6]

可以发现，优化一让排序时间复杂度大大降低，通过添加标记位可以避免多余的比较和交换操作，提高了算法的效率。

结语

冒泡排序虽然时间复杂度比较高，但其算法思想简单直观，容易实现和理解。本篇文章为大家详细介绍了Java语言实现冒泡排序的方式以及针对普通冒泡排序算法的两种优化方法，希望能对大家学习排序算法有所帮助。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：排序算法图解之Java冒泡排序及优化 - Python技术站