基础排序算法（冒泡/选择/插入） - 学习笔记-数据结构与算法-上海佼艾

一、概述

排序算法是计算机科学中最基础、最重要的算法类别之一。无论你是准备面试、编写业务代码还是深入系统底层开发，排序算法都是绕不开的核心知识。在众多排序算法中，冒泡排序（Bubble Sort）、选择排序（Selection Sort）和插入排序（Insertion Sort）是最基础的三种 O(n²) 时间复杂度排序算法。它们虽然在大规模数据场景下性能不如快速排序或归并排序，但因其实现简单、思维直观，是学习算法的最佳入门材料。

这三种算法有一个共同特点：都通过两层循环完成排序，时间复杂度均为 O(n²)。但在实际运行效率、稳定性和适用场景上，它们有着显著差异。更重要的是，对这些基础算法的深入理解，能帮助我们更好地掌握更高级的排序算法——例如，插入排序是希尔排序和 TimSort 的基石。

核心问题：

给定一个包含 n 个元素的数组，如何以升序排列？
三种 O(n²) 算法在什么情况下表现最佳？什么情况下最差？
为什么实际工程中很少使用 O(n²) 排序，但在某些场景下它们又是最优选择？

二、冒泡排序（Bubble Sort）

2.1 核心思想

冒泡排序的得名源于其运作方式：每一轮遍历中，较大的元素会像气泡一样逐渐"浮"到数组的末端。具体做法是重复遍历数组，依次比较相邻的两个元素，如果前一个比后一个大，就交换它们的位置。经过 n-1 轮遍历，数组就完成了排序。

可视化过程（以数组 [5, 3, 8, 4, 2] 为例）：

第一轮：[3, 5, 8, 4, 2] → [3, 5, 8, 4, 2] → [3, 5, 4, 8, 2] → [3, 5, 4, 2, 8]（8 浮到末尾）

第二轮：[3, 5, 4, 2, 8] → [3, 4, 5, 2, 8] → [3, 4, 2, 5, 8]（5 浮到倒数第二位）

第三轮：[3, 4, 2, 5, 8] → [3, 2, 4, 5, 8]（4 浮到倒数第三位）

第四轮：[2, 3, 4, 5, 8]（完成排序）

// 基础冒泡排序实现
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2.2 优化一：提前终止（Early Termination）

如果某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前退出。这个优化使得冒泡排序在最好情况下（数组已经有序）的时间复杂度降至 O(n)。

// 优化版：带提前终止标志
void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 没有交换，已有序
    }
}

2.3 优化二：记录最后交换位置

记录上一轮最后发生交换的位置，该位置之后的元素已经有序，下一轮只需遍历到该位置即可。这对于尾部已经局部有序的数组有显著效果。

// 优化版：记录最后交换位置
void bubbleSortLastSwap(int arr[], int n) {
    int lastSwap = n - 1;
    while (lastSwap > 0) {
        int currentEnd = lastSwap;
        lastSwap = 0;
        for (int j = 0; j < currentEnd; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                lastSwap = j;  // 记录本轮最后交换位置
            }
        }
    }
}

2.4 鸡尾酒排序（Cocktail Shaker Sort）

鸡尾酒排序是冒泡排序的变体。普通的冒泡排序每次只从左到右单向遍历，而鸡尾酒排序交替进行从左到右和从右到左的双向遍历。每轮先正向将最大值送到末尾，再反向将最小值送到开头。这种改进可以更均匀地处理元素移动，减少排序轮数。

// 鸡尾酒排序（双向冒泡）
void cocktailSort(int arr[], int n) {
    int start = 0, end = n - 1;
    bool swapped = true;

    while (swapped) {
        swapped = false;

        // 正向：将最大值移到末尾
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
        end--;
        swapped = false;

        // 反向：将最小值移到开头
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        start++;
    }
}

冒泡排序总结

时间复杂度：最好 O(n)、平均 O(n²)、最差 O(n²)
空间复杂度：O(1)（原地排序）
稳定性：稳定（相等元素不交换，相对顺序不变）
交换次数：等于逆序对数量
优势：实现简单，对于近乎有序的数组性能较好（带优化后）
主要缺点：即使优化后，平均性能仍然远低于插入排序

三、选择排序（Selection Sort）

3.1 核心思想

选择排序的思维方式非常直观：每一轮从未排序区域中找到最小的元素，将其放到已排序区域的末尾。具体做法是：第一轮从整个数组中找到最小值，与第一个位置交换；第二轮从剩下的 n-1 个元素中找到最小值，与第二个位置交换；以此类推，总共执行 n-1 轮。

可视化过程（以数组 [5, 3, 8, 4, 2] 为例）：

第一轮：找到最小值 2，与 arr[0]=5 交换 → [2, 3, 8, 4, 5]

第二轮：从 [3, 8, 4, 5] 中找到最小值 3，已在正确位置 → [2, 3, 8, 4, 5]

第三轮：从 [8, 4, 5] 中找到最小值 4，与 arr[2]=8 交换 → [2, 3, 4, 8, 5]

第四轮：从 [8, 5] 中找到最小值 5，与 arr[3]=8 交换 → [2, 3, 4, 5, 8]

// 选择排序实现
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 在未排序区域 [i, n-1] 中找到最小值
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 将最小值与当前位置交换
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

3.2 选择排序的不稳定性

选择排序是不稳定的。请看下面的例子说明为什么：

示例：考虑数组 [5a, 5b, 3, 1]，其中 5a 和 5b 值相等但用标签区分。

第一轮：找到最小值 1，与 arr[0]=5a 交换，数组变为 [1, 5b, 3, 5a]

注意：5a 和 5b 的相对顺序被改变了！5a 原来在 5b 前面，现在到了 5b 后面。

这就是不稳定性的典型表现——相等元素的相对顺序在排序后无法保证。

3.3 选择排序 vs. 冒泡排序

虽然两者都是 O(n²) 算法，但行为特征差异显著：

对比维度	选择排序	冒泡排序
交换次数	O(n) — 每轮最多一次交换	O(n²) — 每次比较都可能交换
比较次数	O(n²) — 严格 n(n-1)/2 次	O(n²) — 最好 O(n)，平均 O(n²)
稳定性	不稳定	稳定
对有序数组	仍然 O(n²)（无法利用有序性）	优化后可 O(n)（提前终止）
内存写入	极少（交换少）	频繁（交换多）

选择排序的最大优势是交换次数少——最多 n-1 次交换。如果排序的元素非常大（比如每个元素都是一个巨大的结构体），交换操作的代价远高于比较操作，那么选择排序可能优于其他 O(n²) 算法。

四、插入排序（Insertion Sort）

4.1 核心思想

插入排序的思想源于人们整理扑克牌的手动方式：将未排序区域的元素逐个插入到已排序区域的正确位置。具体做法是：从第二个元素开始，将其与前面已排序的元素从后往前逐一比较，找到合适的位置插入（同时将较大元素后移）。

可视化过程（以数组 [5, 3, 8, 4, 2] 为例）：

初始：已排序 [5] | 未排序 [3, 8, 4, 2]

第1步：将 3 插入到 [5] 之前 → [3, 5] | [8, 4, 2]

第2步：将 8 插入到 [5] 之后 → [3, 5, 8] | [4, 2]

第3步：将 4 插入到 [3, 5] 之间 → [3, 4, 5, 8] | [2]

第4步：将 2 插入到最前面 → [2, 3, 4, 5, 8]

// 插入排序实现
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 待插入的元素
        int j = i - 1;

        // 从后往前逐一比较并右移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // 插入到正确位置
    }
}

4.2 最佳情况：近乎有序时接近 O(n)

插入排序有一个非常重要的特性：当输入数组近乎有序时，其性能接近 O(n)。这是因为内层 while 循环几乎不会执行，每个元素只需比较 1~2 次就能找到正确位置。对于"完全有序"的数组，内层循环一次都不执行，只进行 n-1 次外层循环的比较操作。

验证：对已排序数组 [1, 2, 3, 4, 5, 6, 7] 执行插入排序。

第1步：key=2，前面是 1，arr[0]=1 < 2，跳出 while，将 2 放在原位。

第2步：key=3，前面是 2，arr[1]=2 < 3，跳出 while，将 3 放在原位。

... 以此类推，每一轮只执行一次比较，不执行任何元素移动，总比较次数 = n-1。

相比之下，选择排序在完全有序的数组上仍然需要 n(n-1)/2 次比较，完全没有利用输入的特性。这是一个非常重要的区别。

4.3 插入排序与希尔排序的关系

希尔排序（Shell Sort）本质上就是分组的插入排序。它通过先对间隔较大的元素进行排序（让数组快速变得"基本有序"），再逐步缩小间隔，最终在间隔为 1 时进行一次完整的插入排序。由于插入排序对"近乎有序"的数组效率极高，希尔排序的整体性能远优于普通插入排序，平均时间复杂度可达 O(n log n) 到 O(n^1.3) 之间。

// 希尔排序（基于插入排序的分组优化）
void shellSort(int arr[], int n) {
    // 使用希尔增量序列（也可以使用更优的序列如 Hibbard、Sedgewick）
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个分组执行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

可以看到，希尔排序的内核与插入排序完全一致，区别在于：插入排序每次和相邻的前一个元素比较（gap=1），而希尔排序每次和前面间隔 gap 的元素比较。

4.4 插入排序的优势总结

对近乎有序的数据极快 — 实际工程中经常遇到这类数据（如日志数据、部分已完成排序的数据流）
稳定排序 — 相等元素不越过彼此
原地排序 — 只需要 O(1) 额外空间
自适应 — 输入越有序，性能越好
在线算法 — 可以在接收数据的同时进行排序（每次插入一个元素）

五、三种排序详细对比

属性	冒泡排序	选择排序	插入排序
平均时间复杂度	O(n²)	O(n²)	O(n²)
最好时间复杂度	O(n)	O(n²)	O(n)
最差时间复杂度	O(n²)	O(n²)	O(n²)
空间复杂度	O(1)	O(1)	O(1)
稳定性	稳定	不稳定	稳定
比较次数（n=10）	最好 9，平均 ~45，最差 45	固定 45	最好 9，平均 ~45，最差 45
交换次数（n=10）	平均 ~25，最多 45	最多 9	等价于元素移动次数
利用输入有序性	可以（带优化）	不能	非常充分
常用于	教学演示	交换代价极高时	小规模数据、高级排序的基础

综合排名

在绝大多数实际场景下：插入排序 > 冒泡排序 > 选择排序

插入排序胜出是因为它能充分利用输入的有序性，且元素移动比冒泡的频繁交换更高效。实际上，在一次常规的基准测试中，对随机整数数组排序，插入排序通常比冒泡排序快 2~3 倍。

六、排序稳定性的意义

排序的"稳定性"是指：如果两个元素的值相等，排序后它们的相对顺序保持不变。这在某些场景下至关重要。

6.1 多关键字排序

假设有一个学生成绩表，需要先按总分排序，总分相同的学生再按语文成绩排序。一个高效的策略是：先按次要关键字（语文）排序，再按主要关键字（总分）使用稳定排序。由于稳定排序会保留第一次排序的相对顺序，总分相同的学生自然保持了按语文成绩的排序结果。

// 多关键字排序示例：先按语文排序，再按总分稳定排序
// 结果是：总分从高到低，总分相同则语文高的在前

struct Student {
    string name;
    int totalScore;  // 总分
    int chineseScore; // 语文
};

// 第一步：按语文成绩排序
sort(students, students + n, [](const Student& a, const Student& b) {
    return a.chineseScore > b.chineseScore;
});

// 第二步：按总分做稳定排序（如插入排序）
// 稳定排序保证语文成绩的顺序被保留
stableSortByTotalScore(students, n);

6.2 数据库索引

在数据库查询中，如果第一次查询使用了某个索引获得有序结果，第二次排序如果使用不稳定算法可能会打乱第一次的有序性。使用稳定排序可以保证分页查询、分组排序的正确性。

6.3 为什么插入排序是稳定的而选择排序不是？

插入排序在比较时使用 arr[j] > key，当遇到相等元素时，while 循环立即终止，因此相等元素的相对顺序不变。而选择排序在查找最小值时，如果当前元素小于记录的最小值才更新索引，但交换时会将前面的元素直接换到后面去，破坏了相等元素的顺序。

七、插入排序在 TimSort 中的应用

TimSort 是 Python 和 Java 等现代语言内置排序算法（Python 的 list.sort()、Java 的 Arrays.sort() 对对象数组的排序）采用的高效排序算法。它结合了归并排序和插入排序的优势，其中插入排序承担了关键角色。

7.1 TimSort 的核心思路

TimSort 会扫描数组中的 自然有序子序列（run），对于长度小于某个阈值（通常是 32 或 64）的 run，使用插入排序将其扩展到目标长度。利用插入排序在"近乎有序"数据上效率极高的特性，这些 run 的扩展操作非常快。

// TimSort 中插入排序的应用
// 将数组中从 start 到 start+runLen 的范围用插入排序扩展
// 由于二分查找进一步减少了比较次数

void binaryInsertionSort(int arr[], int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        int key = arr[i];
        // 使用二分查找定位插入位置
        int pos = binarySearch(arr, start, i - 1, key);
        // 元素后移并插入
        for (int j = i - 1; j >= pos; j--) {
            arr[j + 1] = arr[j];
        }
        arr[pos] = key;
    }
}

TimSort 中使用的插入排序变体（二分插入排序）进一步将比较次数从 O(n²) 降为 O(n log n)，但元素移动次数仍然是 O(n²)。对于小规模数据（run 的长度 ≤ 64），这完全可接受。

为什么选择插入排序而不是冒泡排序？

TimSort 选择插入排序作为基础算法而非冒泡或选择，原因有三：

插入排序对"近乎有序"的 run 效率极高，而 run 天然具有有序性
插入排序是稳定的，这是 TimSort 的重要保证
插入排序在非常小的数据规模下（如 n < 64），其常数因子远低于归并排序

八、何时使用 O(n²) 排序？

在工业级应用中，大多数场景会选择 O(n log n) 的排序算法（快速排序、归并排序、堆排序、TimSort）。但在以下场景中，O(n²) 排序仍然是最优解：

场景一：数据规模非常小（n < 50）

对于极小的数据集，插入排序的常数因子极低，实际运行速度反而快于快速排序（快速排序的递归调用也有开销）。Java 的 Arrays.sort() 在数据规模小于 47 时就会使用插入排序。

场景二：数据近乎有序

如果确认输入数据已经基本有序（或者只有少量元素错位），插入排序可以达到接近 O(n) 的性能，远快于任何 O(n log n) 算法。

场景三：作为更复杂排序算法的子过程

如 TimSort 和希尔排序所示，插入排序可以作为高级算法的"基础模块"，处理小规模的子问题。

场景四：交换代价极高时

如果每个元素都非常庞大（如内含大量字段的结构体），选择排序只需 n 次交换的优点就非常突出。

场景五：嵌入式/实时系统

在内存极度受限的嵌入式环境中，O(1) 空间复杂度和极简的实现代码是一个重要优势。同时，O(n²) 的确定性能（没有最差情况的退化风险）也符合实时系统的要求。

九、代码实现汇总（Python 版本）

除了 C/C++ 实现外，以下是三种排序算法的 Python 实现，适合快速原型开发和面试准备：

# Python 版三种基础排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr


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


def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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


# 性能对比测试
import random
import time

def benchmark(n=1000):
    data = [random.randint(0, 10000) for _ in range(n)]

    start = time.time()
    bubble_sort(data.copy())
    print(f"冒泡排序: {time.time() - start:.4f}s")

    start = time.time()
    selection_sort(data.copy())
    print(f"选择排序: {time.time() - start:.4f}s")

    start = time.time()
    insertion_sort(data.copy())
    print(f"插入排序: {time.time() - start:.4f}s")

十、面试常见问题与思维拓展

10.1 高频面试题

手写三种排序算法 —— 基本要求，注意边界条件和代码风格
三种排序的区别和应用场景 —— 如上文对比表所示
插入排序在什么时候性能接近 O(n)？ —— 当输入近乎有序时
为什么插入排序比冒泡排序快？ —— 元素移动（一次赋值）比交换（三次赋值）代价低；且插入排序的比较操作更少
如何检验排序算法的稳定性？ —— 构造相等元素，检查相对顺序
能否实现一个 O(n) 的排序？ —— 可以，非比较排序如计数排序、基数排序、桶排序

10.2 进阶思考题

如果将插入排序中的 while 循环改为 for 循环，效率会有什么变化？为什么？
选择排序能否改造成稳定的？如果可以，代价是什么？
冒泡排序的鸡尾酒优化在最坏情况下能否减少元素移动次数？
对于长度为 10 的已排序数组，三种排序分别需要多少次比较和交换？
如何用插入排序的思路实现一个简单的 LRU 缓存？

一、概述

核心问题：

二、冒泡排序（Bubble Sort）

2.1 核心思想

2.2 优化一：提前终止（Early Termination）

2.3 优化二：记录最后交换位置

2.4 鸡尾酒排序（Cocktail Shaker Sort）

冒泡排序总结

三、选择排序（Selection Sort）

3.1 核心思想

3.2 选择排序的不稳定性

3.3 选择排序 vs. 冒泡排序

四、插入排序（Insertion Sort）

4.1 核心思想

4.2 最佳情况：近乎有序时接近 O(n)

4.3 插入排序与希尔排序的关系

4.4 插入排序的优势总结

五、三种排序详细对比

综合排名

六、排序稳定性的意义

6.1 多关键字排序

6.2 数据库索引

6.3 为什么插入排序是稳定的而选择排序不是？

七、插入排序在 TimSort 中的应用

7.1 TimSort 的核心思路

为什么选择插入排序而不是冒泡排序？

八、何时使用 O(n²) 排序？

场景一：数据规模非常小（n < 50）

场景二：数据近乎有序

场景三：作为更复杂排序算法的子过程

场景四：交换代价极高时

场景五：嵌入式/实时系统

九、代码实现汇总（Python 版本）

十、面试常见问题与思维拓展

10.1 高频面试题

10.2 进阶思考题

核心要点总结