Part 3.1：基础排序算法：冒泡、选择与插入

引言：为什么要学习排序？

排序（Sorting）是计算机科学中最基础、最经典的问题之一。无论是数据库查询、搜索引擎排名，还是日常的文件管理，排序无处不在。

虽然现代编程语言都提供了高效的内置排序函数（如 Python 的 sorted()），但深入理解排序算法的原理，对于：

算法思维训练：排序算法涵盖了比较、交换、分治、递归等核心思想。
面试必备：几乎所有技术面试都会涉及排序相关的问题。
性能优化：在特定场景下，选择合适的排序算法能显著提升性能。

本文将带你学习三种最基础的排序算法：冒泡排序、选择排序和插入排序。它们的时间复杂度都是 O(n²)，虽然不是最快的，但它们简单直观，是理解更高级排序算法的基石。

1. 冒泡排序 (Bubble Sort)

直觉：气泡上浮

想象一杯汽水，气泡总是从底部慢慢上浮到顶部。冒泡排序的思想就是：通过多次遍历，每次都让最大的元素像气泡一样”浮”到数组的末尾。

算法原理

从数组的第一个元素开始，比较相邻的两个元素。
如果前一个元素大于后一个元素，就交换它们。
对每一对相邻元素重复步骤 2，直到数组末尾。此时，最大的元素已经”冒泡”到了末尾。
对剩余的 n-1 个元素重复步骤 1-3。
重复 n-1 轮后，数组有序。

动画式案例

初始数组：[5, 3, 8, 4, 2]

第 1 轮（目标：将最大值 8 冒泡到末尾）：

比较 5 和 3：5 > 3，交换 → [3, 5, 8, 4, 2]
比较 5 和 8：5 < 8，不交换 → [3, 5, 8, 4, 2]
比较 8 和 4：8 > 4，交换 → [3, 5, 4, 8, 2]
比较 8 和 2：8 > 2，交换 → [3, 5, 4, 2, 8]

第 2 轮（目标：将次大值 5 冒泡到倒数第二位）：

[3, 4, 5, 2, 8] → [3, 4, 2, 5, 8]

第 3 轮：[3, 2, 4, 5, 8]
第 4 轮：[2, 3, 4, 5, 8] ✅ 完成

伪代码

function bubbleSort(arr):
  n = len(arr)
  for i from 0 to n-1:
    for j from 0 to n-i-2:
      if arr[j] > arr[j+1]:
        swap(arr[j], arr[j+1])

Python 实现（带优化）

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False # 优化：检测是否发生交换
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped: # 如果本轮没有交换，说明已经有序
            break
    return arr

复杂度分析

时间复杂度：
- 最坏情况：O(n²)（逆序）
- 最好情况：O(n)（已有序，带优化）
- 平均情况：O(n²)
空间复杂度：O(1)（原地排序）
稳定性：稳定（相等元素的相对位置不变）

2. 选择排序 (Selection Sort)

直觉：每次选出最小的

想象你在整理扑克牌，每次从未排序的牌中找出最小的一张，放到已排序区域的末尾。

算法原理

在未排序区域中找到最小元素。
将其与未排序区域的第一个元素交换。
将已排序区域扩大一位。
重复步骤 1-3，直到所有元素都被选择。

动画式案例

初始数组：[5, 3, 8, 4, 2]

第 1 轮：在 [5, 3, 8, 4, 2] 中找到最小值 2，与第 1 个元素 5 交换 → [2, 3, 8, 4, 5]
第 2 轮：在 [3, 8, 4, 5] 中找到最小值 3，已在正确位置 → [2, 3, 8, 4, 5]
第 3 轮：在 [8, 4, 5] 中找到最小值 4，与 8 交换 → [2, 3, 4, 8, 5]
第 4 轮：在 [8, 5] 中找到最小值 5，与 8 交换 → [2, 3, 4, 5, 8] ✅

伪代码

function selectionSort(arr):
  n = len(arr)
  for i from 0 to n-1:
    min_index = i
    for j from i+1 to n-1:
      if arr[j] < arr[min_index]:
        min_index = j
    swap(arr[i], arr[min_index])

Python 实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

复杂度分析

时间复杂度：O(n²)（无论什么情况都需要 n²/2 次比较）
空间复杂度：O(1)
稳定性：不稳定（交换可能改变相等元素的相对位置）

3. 插入排序 (Insertion Sort)

直觉：打扑克牌

想象你在打扑克牌，每次抓到一张新牌，你会将它插入到手中已排好序的牌的正确位置。

算法原理

将数组分为”已排序区域”和”未排序区域”。初始时，第一个元素视为已排序。
从未排序区域取出第一个元素。
在已排序区域中从后向前扫描，找到合适的位置并插入。
重复步骤 2-3，直到所有元素都被插入。

动画式案例

初始数组：[5, 3, 8, 4, 2]

第 1 轮：取出 3，插入到 5 前面 → [3, 5, 8, 4, 2]
第 2 轮：取出 8，已在正确位置 → [3, 5, 8, 4, 2]
第 3 轮：取出 4，插入到 5 和 8 之间 → [3, 4, 5, 8, 2]
第 4 轮：取出 2，插入到最前面 → [2, 3, 4, 5, 8] ✅

伪代码

function insertionSort(arr):
  for i from 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j+1] = arr[j]
      j = j - 1
    arr[j+1] = key

Python 实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

复杂度分析

时间复杂度：
- 最坏情况：O(n²)（逆序）
- 最好情况：O(n)（已有序）
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：稳定

4. 三种算法对比

算法	时间复杂度（平均）	空间复杂度	稳定性	特点
冒泡排序	`O(n²)`	`O(1)`	稳定	简单但效率低，适合教学
选择排序	`O(n²)`	`O(1)`	不稳定	交换次数最少（`O(n)`）
插入排序	`O(n²)`	`O(1)`	稳定	对近乎有序的数据效率高

5. 适用场景

插入排序：当数据规模小（n < 50）或数据基本有序时，插入排序非常高效。许多高级排序算法（如快速排序、归并排序）在递归到小规模子问题时，会切换到插入排序。
选择排序：当交换操作成本很高时（如交换大对象），选择排序因其最少的交换次数而有优势。
冒泡排序：实际应用中几乎不用，主要用于教学。