了解冒泡排序算法（附Java示例）

Bubble Sort详解：一个简单的排序算法

冒泡排序是最简单的排序算法之一。它的工作原理是反复比较相邻元素，如果它们顺序不对，则交换它们。例如，如果排序顺序是升序，则比较相邻元素，并将较大的元素放在右边。每次迭代中，我们只比较未排序的元素，并将最大的元素放在数组未排序元素的最后一个位置。

该算法恰如其分地命名为冒泡排序，因为元素在每次迭代中都向数组的右侧移动，就像水泡上升到水面一样。

冒泡排序的工作原理

假设我们要按升序排列这个数组：

第一次迭代

在第一次迭代中，我们尝试将最大元素移动到数组的末尾。因此，我们将重复比较相邻元素，如果它们顺序不对，则交换它们。

已移动到正确位置的元素被认为已排序。

后续迭代

这个过程对所有迭代重复进行，直到数组排序完毕。在每次迭代中，我们只比较未排序的元素，因为已排序的元素已经按正确的顺序排列。

我们迭代遍历数组 n-1 次，其中 n 是数组的长度。也就是说，由于我们的数组有六个元素，我们只迭代遍历数组五次。这是因为，在第五次迭代之后，五个元素已经放置在其正确的位置，因此最终的未排序元素被认为已排序。所有迭代完成后，我们将得到一个排序后的数组。

冒泡排序的实现

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

运行此代码将在控制台中打印以下输出：

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

在这个冒泡排序的实现中，即使数组已经排序，我们也会每次都迭代遍历数组。我们可以进一步优化代码，以便一旦数组已排序就停止排序。

优化的冒泡排序

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

通过这个实现，如果我们尝试对一个已经排序的数组进行排序，我们将只迭代一次，并在没有进行排序时停止。

冒泡排序的复杂度

时间复杂度：

最佳情况 (O(n))：

最佳情况是输入数组已经排序。算法只迭代一次数组以检查它是否已排序，并且不执行任何交换。

平均情况 (O(n²))：

当输入数组元素处于随机顺序时。算法必须进行多次迭代并执行交换以对数组进行排序。

最坏情况 (O(n²))：

最坏情况是输入数组按反向顺序排序。算法进行 n-1 次迭代并执行最大数量的交换。

空间复杂度 O(1)：

冒泡排序是一种就地排序算法，也就是说，它不需要任何与输入数组大小成比例的额外内存。

结论

冒泡排序是一种易于理解和实现的算法。但是，由于其时间复杂度高，因此不适合用于处理大型数据集。在处理小型数据集时，或者当你不关心复杂度时，可以使用冒泡排序。

以上是了解冒泡排序算法（附Java示例）的详细内容。更多信息请关注PHP中文网其他相关文章！