冒泡排序是一种排序算法，它比较两个相邻元素并交换它们，直到它们不符合预期的顺序。就像水中气泡上升到水面的运动一样，数组的每个元素在每次迭代中都移动到最后。因此，它被称为冒泡排序。

• 冒泡排序可以作为排序算法入门与理解
• 现实中因避免使用冒泡排序，效率较差

算法的动画

算法的图解

假设我们试图按升序对元素进行排序。

1. 第一次迭代（比较和交换）
   1. 从第一个索引开始，比较第一个和第二个元素。
   2. 如果第一个元素大于第二个元素，则交换它们。
   3. 现在，比较第二个和第三个元素。如果它们不按顺序交换它们。
   4. 上述过程一直持续到最后一个元素。 | | | —- | | 比较两个相邻元素，如果第一个元素大于下一个元素，则交换它们 |

1. 剩余迭代

对剩余的迭代进行相同的过程。每次迭代后，将未排序元素中最大的元素放在最后。

继续交换并将未排序列表中最大的元素放在最后

在每次迭代中，比较发生到最后一个未排序的元素。

比较相邻元素

当所有未排序的元素都放在正确的位置时，数组就被排序了。

如果所有元素都以正确的顺序排列，则数组已排序

算法的伪码

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

算法的实现

• 冒泡排序一般有两个嵌套循环
  • 外循环运行N次迭代，每次迭代更改未排序区域的起始位置
  • 内部循环在未排序区域进行两两比较，交换并前进的操作
• 冒泡排序会在排序过程中分割成两个区域，已排序区域，未排序区域
• 冒泡排序每一轮内层排序都会在未排序区域中筛选出最大值或最小值

• 如果冒泡排序的某一轮内部循环完全不交换，这意味着数组已经排序，我们可以在这一轮排序后停止冒泡排序。以改进排序性能

  

// Bubble sort in Java
import java.util.Arrays;
class Main {
  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)
        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {
          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }
  public static void main(String args[]) {
    int[] data = { -2, 45, 0, 11, -9 };
    // call method using class name
    Main.bubbleSort(data);
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

算法的优化

在上述算法中，即使数组已经排序，也会进行所有比较。这会增加执行时间。为了解决这个问题，我们可以引入一个额外的变量 swapped。 如果发生元素交换，则 swapped 的值设置为 true。否则，它被设置为 false。
迭代后，如果没有交换，则值 swap 会是 false。这意味着元素已经排序，不需要执行进一步的迭代。这将减少执行时间并有助于优化冒泡排序。

优化冒泡排序的算法是：

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSort

优化的实现

// Optimized Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;

    // loop to access each array element
    for (int i = 0; i < (size-1); i++) {

      // check if swapping occurs
      boolean swapped = false;

      // loop to compare adjacent elements
      for (int j = 0; j < (size-i-1); j++) {

        // compare two array elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;

          swapped = true;
        }
      }
      // no swapping means the array is already sorted
      // so no need for further comparison
      if (!swapped)
        break;

    }
  }

  public static void main(String args[]) {

    int[] data = { -2, 45, 0, 11, -9 };

    // call method using the class name
    Main.bubbleSort(data);

    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

算法复杂度

冒泡排序比较相邻元素。因此，比较的次数是：

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

几乎等于 n2 ，因此，复杂性： O(n2 )。另外，如果我们观察代码，冒泡排序需要两个循环。因此复杂度为：n*n = n2

时间复杂度

• 最坏时间复杂度： 如果我们想按升序排序，而数组按降序排列，那么最坏的情况就会发生。O(n2)
• 最佳时间复杂度： O(n)。如果数组已经排序，则不需要排序。
• 平均时间复杂度： 当数组的元素处于混乱的顺序（既不升也不降）时，就会发生这种情况。O(n2)

空间复杂度

• 空间复杂度是O(1)因为额外的变量用于交换。
• 在优化的冒泡排序算法中，使用了两个额外的变量。因此，空间复杂度为O(2)。

算法的应用

在以下情况下使用计数排序：

• 当复杂度无关紧要
• 简短的代码是首选

相似的算法

• 快速排序
• 插入排序
• 归并排序
• 选择排序