一、什么是排序算法？为什么需要排序？¶

想象你有一堆杂乱的扑克牌，想把它们按大小顺序排列；或者考试后想把同学的成绩从高到低排序；甚至手机里的照片想按拍摄时间从早到晚排列——这些场景都需要“排序”。排序算法，简单说就是把一组无序的数据（比如数字、字符串）变成有序序列（通常是从小到大或从大到小）的方法。

为什么排序很重要？在计算机科学中，排序是最基础也最核心的算法之一。高效的排序算法能让后续的查找、统计等操作更快完成，比如数据库查询优化、数据分析、人工智能中的数据预处理等，都离不开排序。

二、插入排序：像整理扑克牌一样简单¶

基本思想¶

插入排序的核心是“逐步构建有序序列”。可以把它想象成你在整理扑克牌：每次从牌堆里拿出一张未排序的牌，插入到已经排好序的牌堆中的正确位置。

步骤（以数组 [5, 3, 8, 4, 2] 为例）¶

1. 初始状态：数组前1个元素 [5] 已经是“有序牌堆”，剩下的元素 [3, 8, 4, 2] 是未排序的“待插入牌”。
2. 处理第一个待插入元素 3：把 3 与已排序的 5 比较，发现 3 < 5，于是把 5 右移一位，腾出位置插入 3，此时有序牌堆变为 [3, 5]。
3. 处理第二个待插入元素 8：8 与已排序的 5 比较，8 > 5，无需移动，直接插入到末尾，有序牌堆变为 [3, 5, 8]。
4. 处理第三个待插入元素 4：4 与 8 比较（8 > 4），左移一位；再与 5 比较（5 > 4），左移一位；再与 3 比较（3 < 4），停止移动，插入到 3 后面，有序牌堆变为 [3, 4, 5, 8]。
5. 处理最后一个待插入元素 2：2 依次与 8、5、4、3 比较，全部大于 2，左移到最前面，最终数组变为 [2, 3, 4, 5, 8]。

伪代码¶

for i from 1 to n-1:  // 从第二个元素开始遍历（第一个元素默认已排序）
    current = arr[i]  // 当前要插入的元素
    j = i - 1         // 已排序元素的最后一个位置
    while j >= 0 and arr[j] > current:  // 找到插入位置
        arr[j+1] = arr[j]  // 已排序元素右移一位
        j = j - 1          // 继续向左比较
    arr[j+1] = current     // 插入当前元素

优缺点¶

• 时间复杂度：最好情况（已排序数组）是 O(n)（只需遍历一次，无需移动元素）；最坏情况（逆序数组）是 O(n²)（每次都要移动所有已排序元素）；平均情况 O(n²)。
• 空间复杂度：O(1)（原地排序，不需要额外数组）。
• 稳定性：稳定（相等元素不会交换位置）。
• 适用场景：数据量小（比如几百个元素）、接近有序的数据，或者对空间敏感的场景。

三、冒泡排序：像水中气泡“冒”出来一样¶

基本思想¶

冒泡排序的核心是“相邻元素比较交换，大的数‘浮’到顶端”。可以想象水中的气泡，大的气泡会向上浮动，小的气泡会被挤到下方。

步骤（以数组 [5, 3, 8, 4, 2] 为例）¶

1. 第一轮遍历：从第一个元素开始，依次比较相邻元素，若顺序错误则交换。
   - 比较 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]
   - 此时最大的数 8 已“浮”到末尾，第一轮结束。
2. 第二轮遍历：忽略已“浮”到末尾的 8，重复比较前4个元素：
   - 比较 3 和 5：不交换 → [3, 5, 4, 2, 8]
   - 比较 5 和 4：交换 → [3, 4, 5, 2, 8]
   - 比较 5 和 2：交换 → [3, 4, 2, 5, 8]
   - 此时第二大的数 5 已“浮”到倒数第二位，第二轮结束。
3. 重复此过程：每轮“冒泡”会让下一个最大的数就位，直到所有数有序。

伪代码¶

for i from 0 to n-1:  // 遍历数组
    swapped = false   // 标记是否发生交换
    for j from 0 to n-i-2:  // 每轮遍历范围缩小（已冒泡的数不再比较）
        if arr[j] > arr[j+1]:  // 相邻元素顺序错误
            swap(arr[j], arr[j+1])  // 交换
            swapped = true
    if not swapped:  // 若本轮无交换，数组已有序，提前退出
        break

优缺点¶

• 时间复杂度：最好情况（已排序数组）O(n)（提前退出）；最坏和平均情况 O(n²)。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：稳定（相等元素不交换）。
• 适用场景：数据量极小（比如几十个元素）、对代码简洁性要求高的场景（但实际工程中很少用，因为效率低）。

四、归并排序：分治思想的“分而治之”¶

基本思想¶

归并排序是第一个体现“分治思想”的算法。核心是“先分解，后合并”：把数组分成两半，各自排好序，再合并成一个有序数组。可以比喻成把蛋糕切成两半，各自烤好后再拼在一起。

步骤（以数组 [5, 3, 8, 4, 2] 为例）¶

1. 分解：先把数组分成两半，左半 [5, 3] 和右半 [8, 4, 2]；继续分解，直到每个子数组只有1个元素（自然有序）：[5]、[3]、[8]、[4]、[2]。
2. 合并：从最小的子数组开始，两两合并成有序数组：
   - 合并 [5] 和 [3] → [3, 5]；
   - 合并 [8] 和 [4] → [4, 8]；
   - 合并 [2] 单独存在 → [2]；
   - 合并 [3, 5] 和 [4, 8] → [3, 4, 5, 8]；
   - 最后合并 [3, 4, 5, 8] 和 [2] → [2, 3, 4, 5, 8]。

伪代码¶

function mergeSort(arr):
    if 数组长度 <= 1:  // 终止条件：单个元素已有序
        return arr
    mid = 数组长度 // 2  // 中间位置
    left = mergeSort(arr[0..mid-1])  // 递归排序左半
    right = mergeSort(arr[mid..n-1]) // 递归排序右半
    return merge(left, right)  // 合并左右有序数组

function merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  // 取较小元素
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])  // 剩余元素加入
    result.extend(right[j:])
    return result

优缺点¶

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)（分解 log n 次，每层合并 O(n)）。
• 空间复杂度：O(n)（合并时需要额外数组存储结果）。
• 稳定性：稳定（合并时相等元素的相对顺序不变）。
• 适用场景：数据量大（比如几千到几万个元素）、对稳定性要求高的场景（如排序学生成绩时，分数相同的按姓名排序）。

五、快速排序：高效的“分治”实战¶

基本思想¶

快速排序是工程中最常用的高效排序算法，同样基于分治思想，但比归并排序更“灵活”。核心是“选基准，分两半，递归排序”：选一个“基准数”，把数组分成“小于基准”和“大于基准”的两部分，然后递归排序左右两部分。

步骤（以数组 [5, 3, 8, 4, 2] 为例）¶

1. 选基准：这里选第一个元素 5 作为基准数。
2. 分区：把数组分成两部分：所有小于 5 的数在左边，所有大于 5 的数在右边。分区后可能得到 [3, 4, 2, 5, 8]（基准数 5 已在最终位置）。
3. 递归排序：对左边 [3, 4, 2] 和右边 [8] 重复上述过程：
   - 排序 [3, 4, 2]：选基准 3，分区得 [2, 3, 4]；
   - 排序 [8]：单个元素已有序。
4. 合并：最终数组为 [2, 3, 4, 5, 8]。

分区过程（更详细）¶

分区是快速排序的关键，常用方法是“双指针法”：
- 左指针 i 从数组左边开始，右指针 j 从数组右边开始；
- 先移动 i 找到第一个大于基准的元素，再移动 j 找到第一个小于基准的元素，交换 i 和 j 位置；
- 重复直到 i 和 j 相遇，将基准数与相遇位置交换，得到分区结果。

以数组 [5, 3, 8, 4, 2] 为例：
- 基准数 5，i=0，j=4；
- i 指向 5（等于基准，跳过），j 指向 2（小于基准，停止）；
- 交换 i=0 和 j=4 → [2, 3, 8, 4, 5]；
- i 右移到 1（3 < 5，跳过），j 左移到 3（4 < 5，跳过）；
- i=2（8 > 5，停止），j=3（4 < 5，停止）；
- 交换 i=2 和 j=3 → [2, 3, 4, 8, 5]；
- i=3，j=3，相遇，交换基准 5 和 i=3 位置 → [2, 3, 4, 5, 8]。

伪代码¶

function quickSort(arr, left, right):
    if left < right:
        pivotIndex = partition(arr, left, right)  // 分区，返回基准位置
        quickSort(arr, left, pivotIndex - 1)     // 递归左半
        quickSort(arr, pivotIndex + 1, right)    // 递归右半

function partition(arr, left, right):
    pivot = arr[right]  // 选最右边元素为基准（更常用，避免极端情况）
    i = left - 1        // 小于基准的区域边界
    for j from left to right-1:
        if arr[j] <= pivot:
            i += 1      // 扩展小于基准的区域
            swap(arr[i], arr[j])  // 交换到区域内
    swap(arr[i+1], arr[right])  // 基准放到最终位置
    return i + 1  // 返回基准位置

优缺点¶

• 时间复杂度：平均 O(n log n)（基准选得好时）；最坏情况 O(n²)（如数组已排序，且选第一个元素为基准，此时分区后一边为空，另一边 O(n) 长度，递归 log n 次）。
• 空间复杂度：O(log n)~O(n)（递归栈空间，平均 log n，最坏 n）。
• 稳定性：不稳定（相等元素可能被分到不同区域，相对顺序改变）。
• 适用场景：大规模数据（如百万级元素）、工程中最常用（如 Java 的 Arrays.sort() 对基本类型用快速排序）。

六、排序算法对比总结¶

七、初学者学习建议¶

1. 先理解思想：不要死记步骤，先明白“插入排序如何构建有序序列”“快速排序如何分治”。
2. 从简单到复杂：先掌握插入、冒泡排序的直观逻辑，再理解归并排序的“分治”，最后攻克快速排序的“分区”。
3. 动手模拟：用纸上笔写、或在代码编辑器中运行小例子（比如数组 [3,1,4,2]），跟踪每个算法的执行过程。
4. 关注核心差异：比如归并排序的“合并”是关键，快速排序的“分区”是核心，这些是区别于其他算法的本质。

排序算法是算法的“基石”，掌握它们不仅能解决实际问题，更能培养逻辑思维和分治思想，为后续学习更复杂的算法（如堆排序、基数排序）打下基础。

小练习：尝试用插入排序、快速排序分别排序数组 [7, 2, 6, 1, 8]，观察每一步的变化！