1. Introduction

1.介绍

In this quick article, we’ll explore the Bubble Sort algorithm in detail, focusing on a Java implementation.

在这篇快速文章中，我们将详细探讨泡沫排序算法，重点是一个Java实现。

This is one of the most straightforward sorting algorithms; the core idea is to keep swapping adjacent elements of an array if they are in an incorrect order until the collection is sorted.

这是最直接的排序算法之一；核心思想是如果数组中的相邻元素的顺序不正确，就不断地交换它们，直到集合被排序。

Small items “bubble” to the top of the list as we iterate the data structure. Hence, the technique is known as bubble sort.

当我们迭代数据结构时，小项目会 “冒泡 “到列表的顶部。因此，这种技术被称为冒泡排序。

As sorting is performed by swapping, we can say it performs in-place sorting.

由于排序是通过交换进行的，我们可以说它执行的是就地排序。

Also, if two elements have same values, resulting data will have their order preserved – which makes it a stable sort.

此外，如果两个元素具有相同的值，产生的数据将保留它们的顺序 – 这使得它成为一种稳定的排序。

2. Methodology

2.方法学

As mentioned earlier, to sort an array, we iterate through it while comparing adjacent elements, and swapping them if necessary. For an array of size n, we perform n-1 such iterations.

如前所述，为了对一个数组进行排序，我们在比较相邻元素的同时对其进行迭代，必要时进行交换。对于一个大小为n的数组，我们进行n-1这样的迭代。

Let’s take up an example to understand the methodology. We’d like to sort the array in the ascending order:

让我们举一个例子来理解这个方法。我们想将数组按升序排序。

4 2 1 6 3 5

We start the first iteration by comparing 4 and 2; they are definitely not in the proper order. Swapping would result in:

我们从比较4和2开始进行第一次迭代；它们的顺序肯定不对。调换的结果是。

[2 4] 1 6 3 5

Now, repeating the same for 4 and 1:

现在，对4和1重复同样的做法。

2 [1 4] 6 3 5

We keep doing it until the end:

我们一直在做，直到最后。

2 1 [4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

2 1 4 3 [5 6]。

As we can see, at the end of the first iteration, we got the last element at its rightful place. Now, all we need to do is repeat the same procedure in further iterations. Except, we exclude the elements which are already sorted.

我们可以看到，在第一次迭代结束时，我们得到了最后一个元素的正确位置。现在，我们所要做的就是在进一步的迭代中重复同样的程序。只是，我们要排除那些已经被排序的元素。

In the second iteration, we’ll iterate through entire array except for the last element. Similarly, for 3rd iteration, we omit last 2 elements. In general, for k-th iteration, we iterate till index n-k (excluded). At the end of n-1 iterations, we’ll get the sorted array.

在第二次迭代中，我们将迭代整个数组，除了最后一个元素。同样地，对于第三次迭代，我们省略最后两个元素。一般来说，对于第k次迭代，我们迭代到索引n-k（排除）。在n-1迭代结束时，我们将得到排序后的数组。

Now that in you understand the technique, let’s dive into the implementation.

现在你了解了这个技术，让我们深入了解一下实施情况。

3. Implementation

3.实施

Let’s implement the sorting for the example array we discussed using the Java 8 approach:

让我们用Java 8的方法来实现我们讨论的例子数组的排序。

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;
            }
     });
}

And a quick JUnit test for the algorithm:

还有一个关于算法的快速JUnit测试。

@Test
public void whenSortedWithBubbleSort_thenGetSortedArray() {
    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. Complexity and Optimization

4.复杂性和优化

As we can see, for the average and the worst case, the time complexity is O(n^2).

我们可以看到，对于平均和最坏的情况，时间复杂性是O(n^2)。

In addition, the space complexity, even in the worst scenario, is O(1) as Bubble sort algorithm doesn’t require any extra memory and the sorting takes place in the original array.

此外，空间复杂度，即使在最坏的情况下，也是O(1)，因为Bubble排序算法不需要任何额外的内存，而且排序发生在原始数组中。

By analyzing the solution carefully, we can see that if no swaps are found in an iteration, we don’t need to iterate further.

通过仔细分析解决方案，我们可以看到，如果在一次迭代中没有发现交换，我们就不需要进一步迭代。

In case of the example discussed earlier, after the 2nd iteration, we get:

在前面讨论的例子中，在第二次迭代后，我们得到。

1 2 3 4 5 6

In the third iteration, we don’t need to swap any pair of adjacent elements. So we can skip all remaining iterations.

在第三次迭代中，我们不需要调换任何一对相邻的元素。所以我们可以跳过所有剩余的迭代。

In case of a sorted array, swapping won’t be needed in the first iteration itself – which means we can stop the execution. This is the best case scenario and the time complexity of the algorithm is O(n).

如果是一个排序的数组，在第一次迭代本身就不需要交换了–这意味着我们可以停止执行。这是最好的情况，算法的时间复杂度为O(n)。

Now, let’s implement the optimized solution.

现在，让我们来实现优化的解决方案。

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++;
    }
}

Let’s check the output for the optimized algorithm:

让我们检查一下优化后的算法的输出。

@Test
public void 
  givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() {
      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. Conclusion

5.结论

In this tutorial, we saw how Bubble Sort works, and it’s implementation in Java. We also saw how it can be optimized. To summarize, it’s an in-place stable algorithm, with time complexity:

在本教程中，我们看到了泡沫排序的工作原理，以及它在Java中的实现。我们还看到了它是如何被优化的。概括地说，它是一种原地稳定的算法，具有时间复杂性。

Worst and Average case: O(n*n), when the array is in reverse order
Best case: O(n), when the array is already sorted

The algorithm is popular in computer graphics, due to its capability to detect some small errors in sorting. For example, in an almost sorted array, only two elements need to be swapped, to get a completely sorted array. Bubble Sort can fix such errors (ie. sort this array) in linear time.

该算法在计算机图形学中很受欢迎，因为它能够检测到排序中的一些小错误。例如，在一个几乎已经排序的数组中，只需要交换两个元素，就可以得到一个完全排序的数组。泡沫排序可以在线性时间内修复这种错误（即对这个数组进行排序）。

As always, the code for the implementation of this algorithm can be found over on GitHub.

一如既往，该算法的实现代码可以在GitHub上找到over。