【排序算法】冒泡排序

概述

冒泡排序原理

冒泡排序的Java实现

总结

概述

冒泡排序是一种简单但低效的排序算法。它重复地走访要排序的元素列，一次比较两个元素，如果它们的顺序错误就交换它们，直到没有元素需要交换。这个过程类似于气泡在水中上浮的过程，因而得名冒泡排序。

冒泡排序的实现非常简单，但效率较低，特别是在大型数据集上。它的时间复杂度为O(n^2)，其中n是要排序的元素个数。尽管如此，在某些特定情况下，冒泡排序仍然是一种简单且有效的选择。

下面我将详细介绍冒泡排序的原理、实现以及一个Java语言的示例。

冒泡排序原理

冒泡排序的基本思想是通过重复遍历要排序的元素列，比较相邻的两个元素，并根据排序顺序交换它们的位置，直到整个列表排好序为止。排序的过程如下：

从第一个元素开始，依次比较相邻的两个元素，如果第一个元素比第二个元素大（升序排序），则交换它们的位置。
继续向后遍历，重复步骤1，直到比较到倒数第二个元素。
重复以上步骤，每次遍历都将最大的元素“冒泡”到末尾。
每次遍历后，待排序列的末尾就会出现一个已排序的元素，因此每次遍历的范围可以缩小一位。
重复以上步骤，直到没有任何元素需要交换，即列表已经排序完成。

冒泡排序的Java实现

下面是一个用Java语言实现冒泡排序的示例代码：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // 用于标记本次遍历是否有元素交换，若没有则表示列表已排序完成
            for (int j = 0; j < n - 1 - i; 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;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

在这个示例中，我们首先定义了一个名为bubbleSort的静态方法，该方法接受一个整型数组作为参数，并对其进行冒泡排序。然后在main方法中，我们创建了一个整型数组，并调用bubbleSort方法对其进行排序，最后输出排序后的数组。