算法——冒泡排序

算法——冒泡排序

冒泡排序(Bubble Sort)是一种交换排序算法,其核心思想是:通过多次相邻元素之间的比较交换,将数组中的最大(或最小)元素逐步移动到数组的最后(或最前面)。因为最大(或最小)的元素像气泡一样逐渐“冒泡”到数组的边缘,因此得名冒泡排序。

冒泡排序的基本步骤

假设要对一个包含 n个元素的数组进行从小到大的排序:

  1. 从第一个元素开始,比较相邻的两个元素。如果前一个元素比后一个元素大,则交换这两个元素的位置,使得较大的元素后移。
  2. 依次比较相邻的每对元素,不断将较大的元素移动到靠后的位置。
  3. 每完成一次完整的遍历,最大元素会“冒泡”到数组的最后一位(无需再次比较)。
  4. 重复以上过程,对剩下的元素继续比较和交换。每进行一次遍历,待排序的元素数量减少1,直到所有元素排序完成。

冒泡排序的性质

  • 稳定性:冒泡排序是一种稳定的排序算法。稳定性指的是:对于相同的元素,在排序后它们的相对顺序保持不变。因为在冒泡排序中,只有当两个相邻的元素不满足排序要求时,才会进行交换。
  • 时间复杂度
    • 最优时间复杂度:O(n),当输入数据已经是有序时,只需要进行一次遍历,并且没有发生交换。
    • 最坏时间复杂度:O(n2),当输入数据是逆序时,每一次比较都需要交换。
    • 平均时间复杂度:O(n2),无论输入数据的初始顺序如何。
  • 空间复杂度:O(1),因为冒泡排序只需要常数级别的额外空间来交换元素。

冒泡排序的算法演示

以排序数组 [5, 1, 4, 2, 8] 为例,进行冒泡排序的过程如下:

  1. 初始数组[5, 1, 4, 2, 8]
  2. 第一趟排序:
    • 比较 51,因为 5 > 1,交换它们 → [1, 5, 4, 2, 8]
    • 比较 54,因为 5 > 4,交换它们 → [1, 4, 5, 2, 8]
    • 比较 52,因为 5 > 2,交换它们 → [1, 4, 2, 5, 8]
    • 比较 58,因为 5 < 8,不交换 → [1, 4, 2, 5, 8]
    • 第一趟结束,最大值 8 已经在正确位置。
  3. 第二趟排序:
    • 比较 14,因为 1 < 4,不交换 → [1, 4, 2, 5, 8]
    • 比较 42,因为 4 > 2,交换它们 → [1, 2, 4, 5, 8]
    • 比较 45,因为 4 < 5,不交换 → [1, 2, 4, 5, 8]
    • 第二趟结束,次大值 5 已经在正确位置。
  4. 第三趟排序:
    • 比较 12,因为 1 < 2,不交换 → [1, 2, 4, 5, 8]
    • 比较 24,因为 2 < 4,不交换 → [1, 2, 4, 5, 8]
    • 第三趟结束,次次大值 4 已经在正确位置。
  5. 第四趟排序:
    • 比较 12,因为 1 < 2,不交换 → [1, 2, 4, 5, 8]
    • 第四趟结束,数组已经完全有序。

冒泡排序的优化

在某些情况下,数组可能在提前几轮就已经完全有序,因此没有必要继续执行剩下的比较过程。可以通过一个布尔变量 swapped 来记录在每轮遍历中是否有交换发生。如果在某一轮中没有发生交换,表示数组已经有序,可以提前结束排序。

public class OptimizedBubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            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;
            }
        }
    }
}

完整流程总结

  1. 冒泡排序每次遍历会将最大(或最小)元素冒泡到正确位置。
  2. 对每一趟遍历,剩余未排序的部分继续进行比较和交换。
  3. 可以通过优化,避免无效的排序操作,减少时间复杂度。

尽管冒泡排序的思想非常直观,适合教学和小规模数据排序,但由于其时间复杂度较高,在实际应用中通常不适用于大规模数据的排序。

上一篇:排序(插入,希尔,堆排,冒泡)


下一篇:怎么屏蔽统计系统统计到的虚假ip