Bubble Sort详解：一个简单的排序算法
冒泡排序是最简单的排序算法之一。它的工作原理是反复比较相邻元素，如果它们顺序不对，则交换它们。例如，如果排序顺序是升序，则比较相邻元素，并将较大的元素放在右边。每次迭代中，我们只比较未排序的元素，并将最大的元素放在数组未排序元素的最后一个位置。
该算法恰如其分地命名为冒泡排序，因为元素在每次迭代中都向数组的右侧移动，就像水泡上升到水面一样。
假设我们要按升序排列这个数组：
在第一次迭代中，我们尝试将最大元素移动到数组的末尾。因此，我们将重复比较相邻元素，如果它们顺序不对，则交换它们。
已移动到正确位置的元素被认为已排序。
这个过程对所有迭代重复进行，直到数组排序完毕。在每次迭代中，我们只比较未排序的元素，因为已排序的元素已经按正确的顺序排列。
我们迭代遍历数组 n-1 次，其中 n 是数组的长度。也就是说，由于我们的数组有六个元素，我们只迭代遍历数组五次。这是因为，在第五次迭代之后，五个元素已经放置在其正确的位置，因此最终的未排序元素被认为已排序。所有迭代完成后，我们将得到一个排序后的数组。
<code class="language-java">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>运行此代码将在控制台中打印以下输出：
<code>未排序数组: [8, 2, 6, 4, 9, 1] 已排序数组: [1, 2, 4, 6, 8, 9]</code>
在这个冒泡排序的实现中，即使数组已经排序，我们也会每次都迭代遍历数组。我们可以进一步优化代码，以便一旦数组已排序就停止排序。
<code class="language-java">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;
}
}</code>通过这个实现，如果我们尝试对一个已经排序的数组进行排序，我们将只迭代一次，并在没有进行排序时停止。
最佳情况是输入数组已经排序。算法只迭代一次数组以检查它是否已排序，并且不执行任何交换。
当输入数组元素处于随机顺序时。算法必须进行多次迭代并执行交换以对数组进行排序。
最坏情况是输入数组按反向顺序排序。算法进行 n-1 次迭代并执行最大数量的交换。
冒泡排序是一种就地排序算法，也就是说，它不需要任何与输入数组大小成比例的额外内存。
冒泡排序是一种易于理解和实现的算法。但是，由于其时间复杂度高，因此不适合用于处理大型数据集。在处理小型数据集时，或者当你不关心复杂度时，可以使用冒泡排序。
以上是了解冒泡排序算法（附Java示例）的详细内容。更多信息请关注PHP中文网其他相关文章！
