Coding Man冒泡排序
1. 简介
在这篇快速文章中，我们将详细探讨冒泡排序算法，重点是 Java 实现。
这是最直接的排序算法之一；核心思想是 如果数组的相邻元素的顺序不正确，则继续交换它们，直到对集合进行排序。
当我们迭代数据结构时，小项目“冒泡”到列表的顶部。因此，该技术被称为冒泡排序。
由于排序是通过交换执行的，我们可以说它执行就地排序。
此外，如果两个元素具有相同的值，则生成的数据将保留它们的顺序——这使其成为一种稳定的排序 。
2. 方法论
如前所述，为了对数组进行排序，我们在比较相邻元素的同时迭代它，并在必要时交换它们。对于大小为n的数组，我们执行n-1次这样的迭代。
让我们举一个例子来理解这个方法。我们想按升序对数组进行排序：
4 2 1 6 3 5
我们通过比较 4 和 2 开始第一次迭代；它们绝对不是正确的顺序。交换将导致：
[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]
正如我们所看到的，在第一次迭代结束时，我们将最后一个元素放在了正确的位置。现在，我们需要做的就是在进一步的迭代中重复相同的过程。除了，我们排除已经排序的元素。
在第二次迭代中，我们将遍历整个数组，除了最后一个元素。同样，对于第 3 次迭代，我们省略了最后 2 个元素。一般来说，对于第 k 次迭代，我们迭代直到索引nk（排除）。在n-1次迭代结束时，我们将得到排序后的数组。
现在您已经了解了该技术，让我们深入研究实现。
3. 实施
让我们使用 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;
}
});
}
以及对该算法的快速 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. 复杂性和优化
正如我们所见，对于平均情况和最坏情况，时间复杂度为O(n^2)**。
此外，即使在最坏的情况下，空间复杂度也是 O(1)，因为冒泡排序算法不需要任何额外的内存，并且排序发生在原始数组中。
通过仔细分析解决方案，我们可以看到如果在一次迭代中没有找到交换，我们不需要进一步迭代。
对于前面讨论的示例，在第二次迭代之后，我们得到：
1 2 3 4 5 6
在第三次迭代中，我们不需要交换任何一对相邻元素。所以我们可以跳过所有剩余的迭代。
在排序数组的情况下，第一次迭代本身不需要交换——这意味着我们可以停止执行。这是最好的情况，算法的时间复杂度是 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
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);
}