冒泡排序算法详解与实现

排序

简介

问题（排序）
输入： 元素的集合 $A = {a_1, a_2, . . . , a_n}$
输出： 根据指定顺序排列的元素序列 $a_1’, a_2’, …, a_n’$

• 简单但无处不在的问题
• 数据处理的基础操作
• 拥有大量的算法、数据结构和应用场景等
  排序算法通常根据以下指标进行分析：
• 在最坏、最好、平均情况下的比较次数
• 交换次数
• 所需的额外内存
  其他考虑因素：
• 实际考虑：语言支持哪些有序集合（列表、数组等）
• 大多数语言都提供标准（经过优化和充分测试）的排序功能；请使用它！
  排序稳定性：如果“相等”元素的相对顺序得以保持，则称排序算法是稳定的。
• 示例：假设一个列表包含 $10, 2_a, 5, 2_b$；稳定的排序算法将生成 $2_a, 2_b, 5, 10$，而不稳定的排序算法可能会生成 $2_a, 2_b, 5, 10$。
• 稳定的排序对于数据呈现很重要（按两列或两个类别排序）。
• 稳定性取决于所使用的不等式和算法的行为。

在整个过程中，我们将通过表（未排序数组）中的数组来演示排序示例。

4	12	8	1	42	23	7	3

冒泡排序

• 遍历列表，如果相邻的一对元素顺序错误，则交换它们。
• 在第一次遍历结束时，最大元素已经“冒泡”到列表的末尾。
• 将此过程重复 $n$ 次。

伪代码

分析

• 基本操作：比较
• 在第 3 行执行一次
• 内层循环（第 2 行）执行 $n - i$ 次
• 外层循环（第 1 行）执行 $n$ 次
• 总计：$$\sum_{i=1}^n \sum_{j=2}^{n-i+1} 1 = \sum_{i=1}^n (n-i)=n^2-(\sum_{i=1}^n i)=\frac{n^2-n}{2}$$
• 冒泡排序的时间复杂度为 $O(n^2)$。

代码示例

代码示例 9：整数的 Java 冒泡排序

public static void bubbleSort (int array []) {
  int n = array.length;
  int temp = 0;
  for (int i = 0; i < n; i++) {
    for(int j = 1; j < (n-i); j++) {
      if(array[j-1] > array[j]) {
        temp = array[j-1];
        array[j-1] = array[j];
        array[j] = temp;
      }
    }
  }
}