1.简介

在这篇快速文章中,我们将详细探讨冒泡排序算法,当然,重点是Java实现。

冒泡排序是最直接的排序算法之一。

核心思想是:如果数组中的相邻元素顺序不正确,则继续对其进行交换,直到对集合进行排序为止。

当我们迭代数据结构时,小的元素“冒泡”到列表的顶部。因此,该技术被称为气泡排序。

由于排序是通过交换执行的,因此可以说它执行的是原地排序。

另外,如果两个元素具有相同的值,则结果数据将保留其顺序,这使其成为稳定的排序。

不过,尽管这个算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

2.方法

如前所述,要对数组排序,我们在比较相邻元素的同时对其进行迭代,并在必要时交换它们。

对于大小为n的数组,我们需要执行n-1次这样的迭代。

让我们举一个例子来了解这种方法。

我们想按升序对数组进行排序:

4 2 1 6 3 5

我们通过比较4和2开始第1次迭代;他们肯定没有正确的顺序。

交换将导致:

[2 4] 1 6 3 5

现在,对4和1重复相同的操作:

2 [1 4] 6 3 5

我们一直做到最后:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

如我们所见,在第一次迭代结束时,我们将最大元素放到了正确的位置(最后一个元素)。

现在,我们要做的就是在进一步的迭代中重复相同的过程。而且,我们需要排除已经排序的元素。

在第2次迭代中,我们将遍历整个数组,除了最后一个元素。

同样,对于第3次迭代,我们省略了最后2个元素。

通常,对于第k次迭代,我们迭代直到索引nk(不包括在内)。

n-1次迭代结束时,我们将获得排序后的数组。

这里给大家推荐一个网站,可以看动画演示的网站visualgo点击这里

已经了解了该技术,那么让我们深入研究实现。

3.实现

让我们使用Java 8方法为我们讨论的示例数组实现排序:

    public void bubbleSort(Integer[] arr) {
        int n = arr.length;
        IntStream.range(0, n - 1)
                .flatMap(i -> IntStream.range(1, n - i))
                .forEach(j -> {
                    if (arr[j - 1] > arr[j]) {
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                    }
                });
    }

对上面的实现进行单元测试:

@Test
  public void test_BubbleSort() {
    Integer[] array = { 2, 1, 4, 6, 3, 5 };
    Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
    BubbleSort bubbleSort = new BubbleSort();
    bubbleSort.bubbleSort(array);
    assertArrayEquals(array, sortedArray);
  }

4.复杂度和优化

如我们所见,对于平均情况和最坏情况时间复杂度为 O(n ^ 2)

另外,即使在最坏的情况下,空间复杂度也是O(1),因为冒泡排序算法不需要任何额外的内存,并且排序是在原始数组中进行的。

通过仔细分析解决方案,我们可以看到,如果在迭代中未找到任何交换则无需进一步迭代

对于前面讨论的示例,在第2次迭代之后,我们得到:

1 2 3 4 5 6

在第3次迭代中,我们不需要交换任何一对相邻元素。因此,我们可以跳过所有剩余的迭代。

如果是排序数组,则在第1次迭代本身中就不需要交换:这意味着我们可以停止执行。

这是最佳情况**,算法时间复杂度为O(n)**。

现在,让我们实施优化的解决方案。

    public void optimizedBubbleSort(Integer[] arr) {
        int i = 0, n = arr.length;

        boolean swapNeeded = true;
        while (i < n - 1 && swapNeeded) {
            swapNeeded = false;
            for (int j = 1; j < n - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    swapNeeded = true;
                }
            }
            if (!swapNeeded) {
                break;
            }
            i++;
        }
    }

让我们检查优化算法的输出:

    @Test
    public void test_OptimizedBubbleSort() {
        Integer[] array = { 2, 1, 4, 6, 3, 5 };
        Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.optimizedBubbleSort(array);
        assertArrayEquals(array, sortedArray);
    }

5.总结

在本文中,我们看到了冒泡排序的工作原理以及它在Java中的实现。

我们还看到了如何对其进行优化。

总而言之,它是一种就稳定排序算法,具有时间复杂性:

  • 最差和平均情况:O(n * n),当数组以相反顺序排列时
  • 最好的情况:O(n),当数组已经排序时

该算法由于能够检测排序中的一些小错误,因此在计算机图形学中很流行。例如,在几乎排序的数组中,只需交换两个元素即可获得完全排序的数组。冒泡排序可以在线性时间内修复此类错误(即对该数组进行排序)。

与往常一样,可以在GitHub上获得代码示例。