当前位置: 首页 > article >正文

排序-冒泡排序

冒泡排序(Bubble Sort)是一种简单直观的排序算法。它重复地遍历要排序的数组,一次比较两个元素,如果它们的顺序错误就进行交换。遍历数组的工作是重复进行的,直到没有再需要交换,也就是说数组已经排序完成。

下面将详细讲解冒泡排序的原理、步骤、时间复杂度、空间复杂度、优缺点以及优化方法,并提供示例代码来帮助理解。

一、排序原理

冒泡排序的核心思想是通过多次比较和交换,使较大的元素逐渐“冒泡”到数组的末端。具体过程如下:

  1. 比较相邻的元素:从数组的起始位置开始,依次比较每对相邻的元素。
  2. 交换顺序:如果前一个元素比后一个元素大(或根据需要的排序顺序),则交换它们的位置。
  3. 重复遍历:完成一次遍历后,最后的元素是该数组中最大的元素(对于升序排序)。
  4. 迭代进行:对除最后一个元素外的剩余部分重复上述过程,直到整个数组有序。

二、步骤详解

以升序排序为例,具体步骤如下:

  1. 第一轮遍历

    • 从数组的第一个元素开始,依次比较相邻的两个元素。
    • 如果前一个元素大于后一个元素,则交换它们的位置。
    • 经过第一轮遍历后,最大的元素被“冒泡”到数组的末端。
  2. 第二轮遍历

    • 对前 n-1 个元素重复上述步骤,忽略已经排好序的最后一个元素。
    • 经过第二轮遍历后,第二大的元素被排到倒数第二的位置。
  3. 继续迭代

    • 每一轮遍历都将下一个最大元素“冒泡”到合适的位置。
    • 重复此过程,直到整个数组有序。

示例

假设有一个数组 [5, 3, 8, 4, 2],进行升序排序:

  • 第一轮遍历

    1. 比较 53,因为 5 > 3,交换得到 [3, 5, 8, 4, 2]
    2. 比较 58,不交换,数组保持 [3, 5, 8, 4, 2]
    3. 比较 84,因为 8 > 4,交换得到 [3, 5, 4, 8, 2]
    4. 比较 82,因为 8 > 2,交换得到 [3, 5, 4, 2, 8]
    • 第一轮结束,最大元素 8 已经在末端。
  • 第二轮遍历

    1. 比较 35,不交换,数组保持 [3, 5, 4, 2, 8]
    2. 比较 54,因为 5 > 4,交换得到 [3, 4, 5, 2, 8]
    3. 比较 52,因为 5 > 2,交换得到 [3, 4, 2, 5, 8]
    • 第二轮结束,第二大元素 5 已经在倒数第二的位置。
  • 第三轮遍历

    1. 比较 34,不交换,数组保持 [3, 4, 2, 5, 8]
    2. 比较 42,因为 4 > 2,交换得到 [3, 2, 4, 5, 8]
    • 第三轮结束,第三大元素 4 已经在倒数第三的位置。
  • 第四轮遍历

    1. 比较 32,因为 3 > 2,交换得到 [2, 3, 4, 5, 8]
    • 第四轮结束,第四大元素 3 已经在倒数第四的位置。
  • 最终结果:数组已经按升序排列 [2, 3, 4, 5, 8]

三、时间复杂度

  • 最优时间复杂度:O(n)
    当数组已经有序时,只需要进行一次遍历,无需交换。

  • 平均时间复杂度:O(n²)
    无论初始状态如何,通常需要进行多次遍历和交换。

  • 最坏时间复杂度:O(n²)
    当数组完全逆序时,需要进行最多的交换次数。

四、空间复杂度

  • 空间复杂度:O(1)
    冒泡排序是一种原地排序算法,只需要常数级别的额外空间。

五、稳定性

冒泡排序是一种稳定的排序算法。稳定性指的是相同元素的相对顺序在排序后保持不变。由于冒泡排序只在前一个元素大于后一个元素时才进行交换,因此相同元素不会被改变相对位置。

六、优缺点

优点

  1. 实现简单:算法逻辑直观,容易编写和理解。
  2. 稳定性:保持相同元素的相对位置不变。
  3. 空间效率高:仅需常数级别的额外空间。

缺点

  1. 时间效率低下:对于大规模数据,冒泡排序效率较低,性能不佳。
  2. 交换操作频繁:在元素需要移动较远位置时,交换次数较多,影响性能。

七、优化方法

尽管冒泡排序在一般情况下效率较低,但可以通过一些优化措施提高其性能:

1. 提前结束排序

在某一轮遍历中,如果没有发生任何交换,说明数组已经有序,可以提前结束排序,减少不必要的遍历次数。

实现方法

  • 引入一个布尔标志 swapped,初始为 false
  • 在遍历过程中,如果发生交换,则将 swapped 设为 true
  • 遍历结束后,检查 swapped 是否为 true,如果没有交换则终止排序。

示例代码

public void optimizedBubbleSort(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]) {
                // 交换 arr[j] 和 arr[j + 1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 如果没有发生交换,数组已经有序
        if (!swapped) {
            break;
        }
    }
}

2. 记录最后交换的位置

有时数组的后部分可能已经有序,但前面还未完全排序。可以记录每轮遍历中最后一次交换的位置,这样在下一轮遍历时只需遍历到该位置即可,无需遍历整个数组。

实现方法

  • 引入一个变量 lastSwappedIndex,记录最后一次交换的位置。
  • 在下一轮遍历时,只需遍历到 lastSwappedIndex 之前的位置。

示例代码

public void optimizedBubbleSortWithLastSwap(int[] arr) {
    int n = arr.length;
    int lastSwappedIndex;
    int newn;
    newn = n;
    do {
        lastSwappedIndex = newn;
        newn = 0;
        for (int i = 0; i < lastSwappedIndex - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // 交换 arr[i] 和 arr[i + 1]
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                newn = i + 1;
            }
        }
    } while (newn > 0);
}

八、示例代码

下面提供一个完整的冒泡排序示例,包括优化后的版本:

public class BubbleSortExample {

    // 普通冒泡排序
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 优化的冒泡排序(提前结束)
    public static void optimizedBubbleSort(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]) {
                    // 交换 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 optimizedBubbleSortWithLastSwap(int[] arr) {
        int n = arr.length;
        int lastSwappedIndex;
        int newn;
        newn = n;
        do {
            lastSwappedIndex = newn;
            newn = 0;
            for (int i = 0; i < lastSwappedIndex - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    // 交换 arr[i] 和 arr[i + 1]
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    newn = i + 1;
                }
            }
        } while (newn > 0);
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 测试冒泡排序
    public static void main(String[] args) {
        int[] arr1 = {5, 1, 4, 2, 8};
        System.out.println("原始数组:");
        printArray(arr1);

        bubbleSort(arr1);
        System.out.println("普通冒泡排序后:");
        printArray(arr1);

        int[] arr2 = {5, 1, 4, 2, 8};
        optimizedBubbleSort(arr2);
        System.out.println("优化后的冒泡排序(提前结束)后:");
        printArray(arr2);

        int[] arr3 = {5, 1, 4, 2, 8};
        optimizedBubbleSortWithLastSwap(arr3);
        System.out.println("优化后的冒泡排序(记录最后交换位置)后:");
        printArray(arr3);
    }
}

输出结果

原始数组:
5 1 4 2 8 
普通冒泡排序后:
1 2 4 5 8 
优化后的冒泡排序(提前结束)后:
1 2 4 5 8 
优化后的冒泡排序(记录最后交换位置)后:
1 2 4 5 8 

九、何时使用冒泡排序

虽然冒泡排序实现简单且稳定,但由于其时间复杂度较高,通常仅在以下情况下使用:

  1. 小规模数据:对于数据量较小的数组,冒泡排序的性能可以接受。
  2. 教育和学习:冒泡排序是介绍基础排序算法的经典例子,帮助理解排序的基本概念。
  3. 数据接近有序:如果数据已经基本有序,优化后的冒泡排序可以表现出较好的性能。

然而,在实际应用中,对于大规模数据,通常会选择更高效的排序算法,如快速排序(Quick Sort)、归并排序(Merge Sort)或堆排序(Heap Sort)。

十、总结

冒泡排序是一种简单直观的排序算法,通过重复比较和交换相邻元素,将较大的元素逐步“冒泡”到数组的末端。虽然其时间复杂度为O(n²),在处理大规模数据时效率较低,但由于其实现简单和稳定性,仍在教育和某些特定场景下具有应用价值。通过优化策略,如提前结束和记录最后交换位置,可以在一定程度上提高其性能。

理解冒泡排序有助于掌握排序算法的基本原理,并为学习更复杂的排序算法打下基础。


http://www.kler.cn/a/449181.html

相关文章:

  • <论文>初代GPT长什么样?
  • 移动网络(2,3,4,5G)设备TCP通讯调试方法
  • 代码随想录 day52 第十一章 图论part03
  • R 语言 | 绘图的文字格式(绘制上标、下标、斜体、文字标注等)
  • springboot根据租户id动态指定数据源
  • PromptGIP:Unifying lmage Processing as Visual Prompting Question Answering
  • 深入探索Flink的复杂事件处理CEP
  • 2009年408真题解析-数据结构篇(未完)
  • 使用idea创建JDK8的SpringBoot项目
  • 面向对象 类函数的区别 实例方法 类方法 静态方法 抽象方法
  • ensp 基于端口安全的财务部网络组建
  • 【更新】LLM Interview
  • 【工作流】工作顺序
  • Java内区域详解
  • 开源 JS PDF 库比较
  • 4-Gin HTML 模板渲染 --[Gin 框架入门精讲与实战案例]
  • 细说STM32F407单片机DMA方式读写SPI FLASH W25Q16BV
  • Python从0到100(七十九):神经网络-从0开始搭建过拟合和防过拟合模型
  • DINO对比去噪训练代码分析
  • 范德蒙矩阵(Vandermonde 矩阵)简介:意义、用途及编程应用
  • 图学习新突破:一个统一框架连接空域和频域
  • 《开启微服务之旅:Spring Boot 从入门到实践》(一)
  • 短视频矩阵源码开发部署全解析
  • CentOS修改hostname,导致无法连接(网络不工作)
  • 动手学深度学习-深度学习计算-1层和块
  • 如何实现圆形头像功能