数据结构算法

大家想学习更多AI知识，可以收藏下面两个网站：
GPTBUYS、ZeoAPI

排序几乎是所有业务系统都会碰到的基础能力：数据库查询结果展示、日志聚合、搜索结果重排、排行榜计算、批处理去重前预处理，底层都离不开排序。对工程师来说，理解排序算法不只是为了应付面试，更重要的是知道：什么时候应该自己实现，什么时候直接用语言内建排序，什么时候该优先考虑稳定性、空间占用和数据分布特征。

摘要

摘要：本文从工程实践角度梳理八种常见排序算法：冒泡、选择、插入、归并、快速、堆、计数、基数排序。

文章重点不是“背定义”，而是回答三个更实际的问题：

  1. 这些排序到底差在哪？
  2. 什么场景应该选哪一种？
  3. 为什么工业实现里常常不是直接使用教科书中的单一算法？

结合近期资料可知，常见排序可分为比较排序与非比较排序两大类；稳定性、时间复杂度、空间复杂度是最核心的评估维度。[1][4][6] 同时，Python 官方文档明确说明 list.sort() 和 sorted() 使用的是 Timsort，它融合了归并排序与插入排序思想，强调稳定性以及对“局部有序数据”的利用，这也是工程实践中非常重要的思路。[2]

排序算法的核心评价维度

摘要：选排序算法前，先看复杂度、稳定性、空间占用和数据特征，而不是只盯平均时间复杂度。

工程上比较排序算法，通常会从下面几个维度入手：

1）时间复杂度

最常见的是：

  • O(n^2)：如冒泡、选择、插入
  • O(n log n)：如归并、快速、堆
  • 线性级别或接近线性：如计数、基数，但前提是满足特定数据条件 [1][6]

2）空间复杂度

  • 原地排序更适合内存敏感场景，比如快速排序、堆排序通常更省额外空间
  • 归并排序通常需要额外辅助空间
  • 计数排序需要额外计数数组，当值域很大时开销会很明显 [1]

3）稳定性

稳定性指：若两个元素排序键相等，排序后它们的相对顺序是否保持不变。[4][6]

这在多关键字排序中非常关键。比如先按“部门”排，再按“薪资”排，如果第二轮排序是稳定的，就能保留第一轮排序的结果。资料中常见结论是：

  • 通常稳定：冒泡、插入、归并、计数 [4]
  • 通常不稳定：选择、快速、堆 [4]

4）输入数据特征

工程场景里，数据不是随机教科书数组：

  • 可能已经部分有序
  • 可能重复值很多
  • 可能值域很小
  • 可能内存非常紧张

比如 Python 的 Timsort 就是利用了数据中的已有顺序，因此在真实业务中表现很优秀。[2]

八种常见排序算法逐个分析

摘要：八种常见排序各有定位，学习时要记“工作机制 + 适用场景 + 代价”。

下面按“从基础到工程常用”的顺序总结。

1）冒泡排序（Bubble Sort）

思路：反复比较相邻元素，如果逆序就交换，较大元素逐轮“冒”到后面。[7]

特点：

  • 时间复杂度平均/最坏通常为 O(n^2)
  • 可优化：一轮没有交换时提前结束
  • 通常稳定 [4]
  • 工程中效率较低，更多用于教学而不是生产 [7]

适用：

  • 代码教学
  • 数据规模很小
  • 需要快速写出最直观实现

2）选择排序（Selection Sort）

思路：每轮从未排序区间中选出最小值，放到当前起始位置。

特点：

  • 时间复杂度通常 O(n^2)
  • 交换次数相对少
  • 通常不稳定 [4]

适用：

  • 对“交换成本高、比较成本低”的简单场景可作为基础方案
  • 实际业务中较少直接使用

3）插入排序（Insertion Sort）

思路：维护前缀有序区，把当前元素插入到正确位置。

特点：

  • 平均/最坏 O(n^2)，但对小规模或接近有序数据效果好
  • 通常稳定 [4]
  • 是很多工业级混合排序的重要组成部分 [2]

适用：

  • 小数组
  • 局部有序数据
  • 作为归并/Timsort 等的子过程

4）归并排序（Merge Sort）

思路：分治。先递归拆分，再将两个有序子序列合并。

特点：

  • 时间复杂度稳定在 O(n log n)
  • 通常稳定 [4]
  • 需要额外空间做合并 [1]

适用：

  • 需要稳定性
  • 大规模数据排序
  • 外部排序、链表排序等场景中常见

5）快速排序（Quick Sort）

思路：选定基准值 pivot，把序列划分成小于和大于基准的两部分，再递归处理。

特点：

  • 平均性能优秀，通常为 O(n log n)
  • 最坏可能退化到 O(n^2)
  • 通常不稳定 [4]
  • 常数因子往往较好，因此工程上很常见 [1][5]

适用：

  • 通用内存排序
  • 对平均性能敏感的场景

6）堆排序（Heap Sort）

思路：基于二叉堆，先建堆，再反复取出堆顶元素完成排序。[3]

特点：

  • 时间复杂度通常 O(n log n) [3]
  • 额外空间较低，可视为对选择排序的优化 [3]
  • 通常不稳定 [4]
  • 常数因子可能高于归并排序 [3]

适用：

  • 想要 O(n log n) 且额外空间较低
  • 内存受限但不强依赖稳定性

7）计数排序（Counting Sort）

思路：统计每个值出现次数，再据此回填有序结果。

特点：

  • 非比较排序 [1][6]
  • 当值域 k 不大时，可达到 O(n + k)
  • 通常稳定（稳定实现方式下）[4]
  • 依赖整数或可映射到有限值域的数据

适用：

  • 年龄、分数、状态码等值域有限数据
  • 重复值较多的整数数据

8）基数排序（Radix Sort）

思路：按个位、十位、百位等位数逐轮排序，通常依赖稳定子排序（常见是计数排序）。[1]

特点：

  • 非比较排序 [1]
  • 适合整数或固定格式字符串
  • 性能与位数、基数选择有关
  • 工程上适合特定数据结构，不是通用替代品

适用：

  • 大量定长整数
  • 身份编号、固定宽度编码等结构化数据

Key Comparison Table

摘要：下面这张表用于做工程选型，不追求“绝对最优”，而是帮助快速做出可落地判断。

Dimension 冒泡/选择/插入 归并 快速 堆 计数/基数
核心类别 比较排序 比较排序 比较排序 比较排序 非比较排序
典型时间复杂度 多为 O(n^2) O(n log n) 平均 O(n log n)，最坏 O(n^2) O(n log n) 常见为 O(n+k) 或与位数相关
稳定性 冒泡/插入通常稳定，选择通常不稳定 通常稳定 通常不稳定 通常不稳定 计数通常稳定；基数依赖稳定子排序
额外空间 一般较低 通常较高，需要辅助数组 一般较低 较低 与值域或桶/计数结构相关
适用场景 小规模、教学、近乎有序数据 需要稳定性、大规模数据 通用内存排序、平均性能优先 内存敏感且要求 O(n log n) 值域有限、结构化整数数据
工程建议 很少单独用于生产主流程 稳定排序优先考虑 常见默认候选，但要注意最坏情况 可作为空间友好方案 满足数据前提时非常高效

工程实践中如何选择

摘要：真正上线时，通常不是“学会哪一个就用哪一个”，而是先判断数据特征，再决定是否直接使用标准库。

下面给出一份实用决策树：

场景 1：业务系统普通排序

优先用语言标准库。
原因很简单：标准库通常经过多年优化与验证，边界处理、稳定性、局部有序利用、实现常数都优于手写版。

例如 Python 官方文档说明，其排序使用 Timsort，是一种结合归并排序和插入排序思想的稳定排序，能够有效利用已有有序片段。[2]

场景 2：需要稳定性

优先考虑：

  • 归并排序
  • 标准库稳定排序
  • 计数排序（前提满足）

多关键字排序尤其依赖稳定性。[4]

场景 3：值域很小的整数数据

优先考虑：

  • 计数排序
  • 基数排序（如果是多位整数或固定格式键）

这是非比较排序的优势区间。[1]

场景 4：内存比较紧张

优先考虑：

  • 堆排序
  • 原地快速排序实现

其中堆排序通常能提供较低额外空间，同时保持 O(n log n) 级别复杂度。[3]

场景 5：数据规模小或基本有序

优先考虑：

  • 插入排序
  • 或混合排序中的小数组分支

这也是插入排序在工业实现中长期存在的原因之一。[2]

实战代码示例

摘要：下面给出两个常用实现，一个用于理解排序机制，一个用于体现工程上更推荐的调用方式。

示例 1：Python 实现插入排序

def insertion_sort(nums):
    # 目的：对列表进行原地插入排序
    for i in range(1, len(nums)):
        key = nums[i]          # 当前待插入元素
        j = i - 1

        # 将比 key 大的元素整体右移
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1

        # 把 key 放到合适位置
        nums[j + 1] = key

    return nums


data = [5, 2, 4, 6, 1, 3]
print(insertion_sort(data))

工程点评：

  • 插入排序代码短、易读，非常适合讲清“局部有序”思想。
  • 当数组很小或者基本有序时，它往往并不差。
  • 但大规模随机数据下，不建议作为主排序方案。

示例 2：Java 实现堆排序

import java.util.Arrays;

public class HeapSortDemo {

    // 目的：执行堆排序主流程
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 第一步：构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 第二步：依次把堆顶最大值放到数组末尾
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);         // 交换堆顶和当前末尾
            heapify(arr, i, 0);      // 重新调整剩余区间为大顶堆
        }
    }

    // 作用：维护以 i 为根的子树满足大顶堆性质
    private static void heapify(int[] arr, int heapSize, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 找到根、左、右三个位置中的最大值
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }

        // 若根不是最大值，则交换并继续向下调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, heapSize, largest);
        }
    }

    // 工具方法：交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

工程点评：

  • 堆排序的核心不在“交换”，而在“维护堆结构”。
  • 当你既要 O(n log n)，又不希望像归并排序那样引入明显辅助数组时，堆排序是可靠备选。[3]

代码块注释规范

摘要：技术博客里的代码注释要服务于理解与复现，避免“翻译代码式注释”。

建议遵循以下 4 条规则：

  1. 先写代码块目的
    在函数或代码块开头说明“这段代码要解决什么问题”，不要让读者自己猜。

  2. 只注释关键步骤
    比如“构建堆”“递归划分”“计数回填”，不必每一行都加废话注释。

  3. 解释算法不变量
    例如插入排序中“前缀区间始终有序”，堆排序中“当前子树需满足大顶堆性质”。

  4. 标出复杂度敏感点
    如递归、额外数组分配、双层循环等，这能帮助读者快速抓住性能重点。

  5. 注释要与代码同步更新
    注释过期比没有注释更危险，尤其在博客示例中容易误导读者复制使用。

常见问题与排错

摘要：排序代码最容易错在边界、稳定性误判和复杂度预期错误。

1）快速排序为什么有时会很慢？

如果基准选择不佳，快速排序可能退化到 O(n^2)。[1] 对近乎有序数组尤其要小心。

2）“稳定排序”到底有什么用？

当你做多关键字排序时，稳定性能保留前一次排序结果，这在业务字段组合排序中非常重要。[4]

3）计数排序为什么不能乱用？

因为它依赖值域。如果最大最小值跨度极大，计数数组会导致空间浪费。[1]

4）堆排序明明也是 O(n log n)，为什么不总比归并好？

因为实际工程里常数因子、缓存局部性、稳定性都很关键。资料指出堆排序常数因子可能高于归并排序。[3]

5）为什么标准库排序通常比手写快？

标准库经过长期优化，往往是混合排序策略，并对边界情况做了充分处理。Python 的 Timsort 就是典型例子。[2]

结论与下一步建议

摘要：学习排序的关键不是背 8 个名字，而是建立“场景—约束—算法”的映射关系。

如果你只记住一句话，我建议是：

  • 小规模或近乎有序：插入排序思想很有价值
  • 需要稳定性：优先归并/稳定标准库
  • 平均性能优先：快速排序常见
  • 内存更敏感：堆排序可考虑
  • 值域有限整数：计数/基数排序更有优势
  • 真实项目里：优先使用标准库，而不是重复造轮子

下一步建议你继续做两件事：

  1. 自己手写一遍 插入、快速、堆、归并 四种排序；
  2. 对同一批数据分别测试“随机数组、近乎有序数组、重复值很多数组”的耗时差异。

只有跑过实验，排序算法才会从“概念”变成真正的工程判断力。

参考资料

  • Sorting Algorithms - GeeksforGeeks
    https://www.geeksforgeeks.org/dsa/sorting-algorithms/

  • Sorting Techniques — Python 3.14.4 documentation
    https://docs.python.org/3/howto/sorting.html

  • Heap Sort - GeeksforGeeks
    https://www.geeksforgeeks.org/dsa/heap-sort/

  • Stable and Unstable Sorting Algorithms - GeeksforGeeks
    https://www.geeksforgeeks.org/dsa/stable-and-unstable-sorting-algorithms/

  • Sorting in Java - GeeksforGeeks
    https://www.geeksforgeeks.org/java/sorting-in-java/

  • Sorting algorithm
    https://en.wikipedia.org/wiki/Sorting_algorithm

  • Bubble sort
    https://en.wikipedia.org/wiki/Bubble_sort

# 排序算法 # 数据结构 # 算法 # 人工智能
Logo
DeepSeek技术社区

欢迎加入DeepSeek 技术社区。在这里，你可以找到志同道合的朋友，共同探索AI技术的奥秘。

更多推荐

Headroom上下文压缩引擎架构拆解：六层管道如何让AI Agent的Token消耗降低60-95%

Headroom是一款面向AI Agent的透明压缩层工具，基于Rust核心+Python SDK架构，可显著降低Token使用成本。该工具通过六层处理管道实现智能压缩：1）前缀稳定化以优化KV缓存命中；2）内容类型识别路由；3）6种自适应压缩算法（代码/JSON/日志等）；4）可逆压缩存储机制；5）对话上下文智能裁剪；6）跨Agent记忆共享。支持四种部署模式，最高可节省95%的Token消耗，

avatar DeepSeek技术社区

上下文工程 vs 提示词工程：决定 Agent 上限的，是前者不是你天天调的那玩意

诊断并优化你的 AI Agent / LLM 应用的上下文窗口使用效率。自动检测上下文膨胀、冗余检索、无效工具调用、提示词过长等问题，输出可执行的优化方案——涵盖上下文隔离、修剪、压缩总结、动态工具装载与外部卸载五大策略。适用于 Claude Code、LangChain、LangGraph、Dify、AgentScope 等主流 Agent 框架。

avatar DeepSeek技术社区

用AI搭建你的论文论证框架——图尔敏模型 (Toulmin Model) × ChatGPT实战指南

让我先讲个故事。想象一场法庭审判。法官面前的被告需要证明自己的清白。律师不能只说"我的当事人无辜"，还必须提供证据、解释逻辑、预见对方反驳……最终由陪审团（相当于受众）判决。法庭的这套论证机制，正是任何有效论证都该遵循的逻辑。与古典修辞学的三段论（所有人都会死→苏格拉底是人→因此苏格拉底会死）不同，图尔敏模型更贴近真实世界的论证：它承认论证很少达到"绝对确定"，因此强调理由、证据、假设、反驳预案的

avatar DeepSeek技术社区