泡泡排序

admin

泡泡排序（Bubble Sort）是一种简单的比较排序算法，属于交换排序的一种。其主要思想是通过重复遍历待排序的数列，比较相邻元素并交换它们的位置，从而将未排序部分中的最大（或最小）元素“浮”到数列的顶端（或底端）。算法的名字来源于这种“浮”现象，类似于气泡在水中向上升起。
算法步骤

• 从头开始遍历：从数组的第一个元素开始，依次比较相邻的两个元素。
• 比较并交换：如果当前元素大于下一个元素，则交换它们的位置。
• 重复遍历：对每一对相邻元素进行比较和交换，直到遍历完整个数组。此时，最大的元素将被“浮”到最后一位。
• 减少遍历范围：每完成一次遍历，可将最后一个元素视为已排序，下一次遍历时不再比较它。
• 终止条件：当一轮遍历中没有进行任何交换时，说明数组已排序，可以提前结束。
  

示例考虑一个简单的数组：[5, 3, 8, 4, 2]

• 第一轮：
  
  • 比较 5 和 3，交换 -> [3, 5, 8, 4, 2]
  • 比较 5 和 8，不交换
  • 比较 8 和 4，交换 -> [3, 5, 4, 8, 2]
  • 比较 8 和 2，交换 -> [3, 5, 4, 2, 8]
    
• 第二轮：
  
  • 比较 3 和 5，不交换
  • 比较 5 和 4，交换 -> [3, 4, 5, 2, 8]
  • 比较 5 和 2，交换 -> [3, 4, 2, 5, 8]
  • 至此，8 已经确定为最大
    
• 第三轮：
  
  • 比较 3 和 4，不交换
  • 比较 4 和 2，交换 -> [3, 2, 4, 5, 8]
    
• 第四轮：
  
  • 比较 3 和 2，交换 -> [2, 3, 4, 5, 8]
    

经过多轮比较和交换，最终得到排序结果：[2, 3, 4, 5, 8]
时间复杂度

• 最坏情况和平均情况：O(n²)，当输入数组逆序时，需要进行大量的比较和交换。
• 最好情况：O(n)，当输入数组已经是有序时，只需要进行一轮遍历，判断没有进行交换。
  

空间复杂度

• O(1)，因为只需要常量级别的额外空间来存储临时变量。
  

优缺点优点：

• 实现简单，容易理解。
• 在数据量小的情况下，效率较高。
  

缺点：

• 效率低下，不适合数据量较大的情况。
• 在大多数情况下，不如其他复杂度更低的排序算法（如快速排序、归并排序等）高效。
  

泡泡排序主要用于学习和理解排序算法的基本概念，而不是在实际应用中广泛使用。