排序是计算机科学中最基础且核心的操作之一，其目的是将一组无序数据按照特定规则（如升序、降序）重新排列。不同排序算法在时间复杂度、空间复杂度、稳定性和适用场景上差异显著，选择合适的排序方法是优化程序性能的关键。以下将详细介绍计算机常用的 10 种排序方法，从基本原理到特性对比进行全面解析。
一、排序算法核心概念（前置知识）
在介绍具体算法前，需明确 3 个关键评价指标，这是区分不同排序的核心依据：
- 时间复杂度：描述算法执行时间随数据规模（n）增长的趋势，通常关注最坏情况和平均情况，常见量级为 O (n²)（简单排序）、O (n log n)（高效排序）、O (n)（线性排序，需特殊条件）。
- 空间复杂度：描述算法执行过程中额外占用的存储空间，分为原地排序（O (1)，仅用少量临时变量）和非原地排序（O (n)，需额外数组或栈 / 队列）。
- 稳定性：若数据中存在值相等的元素，排序后其相对位置不发生改变，则为稳定排序；否则为不稳定排序（稳定排序在多字段排序场景中至关重要，如 “先按成绩排序，再按姓名排序”）。
二、常用排序算法详解
1. 冒泡排序（Bubble Sort）—— 最简单的排序
基本原理
通过相邻元素两两比较，将值较大（或较小）的元素逐步 “冒泡” 到数组末端。每一轮遍历后，未排序区间的最大元素会确定最终位置，重复此过程直到所有元素有序。
- 优化点：若某一轮遍历中未发生任何交换，说明数组已有序，可直接退出（避免无效循环）。
执行步骤（升序为例）
- 从数组第 1 个元素开始，依次比较相邻的两个元素（如 arr [0] 与 arr [1]、arr [1] 与 arr [2]）；
- 若前一个元素 > 后一个元素，则交换两者位置；
- 一轮遍历结束后，数组末尾会多一个有序元素（最大元素）；
- 缩小未排序区间，重复步骤 1-3，直到未排序区间长度为 1。
特性
- 时间复杂度：最坏 O (n²)（完全逆序）、平均 O (n²)、最好 O (n)（已有序，优化后）；
- 空间复杂度：O (1)（原地排序）；
- 稳定性：稳定（相等元素不交换）；
- 适用场景：小规模数据（n≤100）、几乎有序的数据（优化后效率高）。
2. 选择排序（Selection Sort）——“选最小的放前面”
基本原理
将数组分为 “已排序区间” 和 “未排序区间”，每一轮从未排序区间中找到最小值（或最大值） ，将其与未排序区间的第一个元素交换，逐步扩大已排序区间。
执行步骤（升序为例）
- 初始时，已排序区间为空，未排序区间为整个数组；
- 遍历未排序区间，找到最小值的索引 min_idx；
- 将 arr [min_idx] 与未排序区间的第一个元素（arr [i]，i 为当前轮次的起始索引）交换；
- 已排序区间长度 + 1，未排序区间长度 - 1，重复步骤 2-3，直到未排序区间为空。
特性
- 时间复杂度：最坏 / 平均 / 最好均为 O (n²)（无论数据是否有序，都需遍历找最小值）；
- 空间复杂度：O (1)（原地排序）；
- 稳定性：不稳定（例如数组 [3, 2, 3, 1]，第一轮会将第 1 个 3 与 1 交换，导致两个 3 的相对位置改变）；
- 适用场景：小规模数据、对稳定性无要求的场景（如纯数值排序）。
3. 插入排序（Insertion Sort）——“摸牌式排序”
基本原理
类比打牌时 “摸一张牌，插入到手中已有序牌的正确位置”。将数组分为 “已排序区间”（初始为第 1 个元素）和 “未排序区间”，每一轮从未排序区间取第一个元素，插入到已排序区间的合适位置，保持已排序区间有序。
执行步骤（升序为例）
- 已排序区间初始为 [arr [0]]，未排序区间为 [arr [1], arr [2], ..., arr [n-1]]；
- 取未排序区间的第一个元素 x = arr [i]（i 从 1 开始）；
- 在已排序区间中从后向前遍历，将大于 x 的元素依次向后移动一位；
- 找到 x 的插入位置，将 x 放入该位置；
- 已排序区间长度 + 1，重复步骤 2-4，直到未排序区间为空。
特性
- 时间复杂度：最坏 O (n²)（完全逆序，每次插入需移动所有已排序元素）、平均 O (n²)、最好 O (n)（已有序，无需移动元素）；
- 空间复杂度：O (1)（原地排序）；
- 稳定性：稳定（相等元素插入到后面，不改变相对位置）；
- 适用场景：小规模数据（n≤1000）、几乎有序的数据（效率接近 O (n)）、链表排序（无需移动元素，仅修改指针）。
4. 希尔排序（Shell Sort）——“插入排序的优化版”
基本原理
由 Donald Shell 提出，核心是 **“分组插入排序”**：通过设定一个 “步长”（gap），将数组分为多个子数组（每个子数组由间隔为 gap 的元素组成），对每个子数组执行插入排序；逐步缩小步长（如 gap=gap/2），重复分组和插入排序，直到步长为 1（此时数组接近有序，再执行一次普通插入排序）。
执行步骤（升序为例）
- 初始步长 gap = n/2（n 为数组长度）；
- 按 gap 分组，对每组执行插入排序（如 gap=3 时，数组分为 [arr [0], arr [3], arr [6]...]、[arr [1], arr [4], arr [7]...] 等）；
- 缩小步长（如 gap=gap/2，向下取整），重复步骤 2；
- 当 gap=1 时，执行最后一次插入排序，数组完全有序。
特性
- 时间复杂度：取决于步长选择，常见步长（gap=n/2）下平均 O (n log n)，最坏 O (n²)；最优步长（如 Hibbard 步长）可达到 O (n^(3/2))；
- 空间复杂度：O (1)（原地排序）；
- 稳定性：不稳定（分组排序时，相等元素可能被分到不同组，导致相对位置改变）；
- 适用场景：中规模数据（n≤10^4），效率优于简单排序（冒泡、选择、插入）。
5. 归并排序（Merge Sort）——“分而治之” 的典范
基本原理
基于 “分治法” 思想：将数组递归拆分为两个子数组，直到每个子数组只有 1 个元素（天然有序）；然后逐步合并两个有序子数组，最终得到完整的有序数组。合并过程是核心（需额外空间存储临时合并结果）。
执行步骤（升序为例）
- 分解：将数组 arr [low..high] 拆分为 arr [low..mid] 和 arr [mid+1..high]（mid=(low+high)/2），递归分解直到 low==high；
- 合并：创建临时数组 tmp，用两个指针 i（指向左子数组起始）、j（指向右子数组起始），比较 arr [i] 和 arr [j]，将较小值放入 tmp；
- 若某一子数组遍历完，将另一子数组剩余元素全部放入 tmp；
- 将 tmp 中的元素复制回原数组 arr [low..high]，完成一次合并。
特性
- 时间复杂度：最坏 / 平均 / 最好均为 O (n log n)（递归深度为 log n，每一层合并需 O (n) 时间）；
- 空间复杂度：O (n)（需临时数组存储合并结果，递归栈空间为 O (log n)，可忽略）；
- 稳定性：稳定（合并时，左子数组元素若与右子数组相等，优先放入左子数组元素，保持相对位置）；
- 适用场景：大规模数据（n≤10^6）、对稳定性有要求的场景（如对象排序）；缺点是需额外空间，不适合内存受限场景。
6. 快速排序（Quick Sort）——“最快的通用排序”
基本原理
同样基于 “分治法”，核心是选择 “基准元素”（pivot） ，将数组分为 “小于基准的左区间”、“基准”、“大于基准的右区间”；然后递归对左、右区间执行快速排序，最终合并为有序数组。基准的选择直接影响排序效率。
执行步骤（升序为例）
- 选择基准：常见选择方式 —— 固定基准（如第一个元素）、随机基准（避免最坏情况）、三数取中（取左、中、右三个元素的中位数，最优）；
- 分区（Partition）：用指针 i（左）、j（右）遍历数组，将小于基准的元素移到左区间，大于基准的移到右区间，基准放到最终位置 k；
- 递归排序：对左区间 arr [low..k-1] 和右区间 arr [k+1..high] 重复步骤 1-2；
- 递归终止条件：low ≥ high（子数组长度≤1）。
特性
- 时间复杂度：平均 O (n log n)（基准选择合理时）、最好 O (n log n)、最坏 O (n²)（基准选到最值，如已排序数组选第一个元素）；
- 空间复杂度：O (log n)（递归栈空间，平均深度 log n；最坏 O (n)，可通过 “尾递归优化” 或 “迭代实现” 降低）；
- 稳定性：不稳定（分区时，基准元素与其他元素交换可能破坏相等元素的相对位置）；
- 适用场景：大规模数据（n≤10^7）、对空间要求不高的场景；是工业界最常用的排序算法（如 C++ STL 的
sort函数底层实现）。
7. 堆排序（Heap Sort）——“利用堆的特性排序”
基本原理
基于 “堆” 数据结构（完全二叉树）：先将数组构建为大顶堆（父节点≥子节点，用于升序排序）；然后反复将堆顶元素（最大值）与堆尾元素交换，缩小堆的规模并 “调整堆”（保持大顶堆特性），直到堆为空。
执行步骤（升序为例）
- 构建大顶堆：从最后一个非叶子节点（索引 n/2 -1）开始，向前遍历每个节点，执行 “堆调整”（若节点值小于子节点，交换并递归调整子节点）；
- 排序阶段：将堆顶元素（arr [0]，最大值）与堆尾元素（arr [i]，i 从 n-1 开始）交换；
- 堆的规模缩小 1（忽略已交换到末尾的最大值），对新堆顶执行 “堆调整”；
- 重复步骤 2-3，直到堆的规模为 1，数组完全有序。
特性
- 时间复杂度：最坏 / 平均 / 最好均为 O (n log n)（构建堆 O (n)，排序阶段每轮调整 O (log n)，共 n 轮）；
- 空间复杂度：O (1)（原地排序，仅用少量临时变量）；
- 稳定性：不稳定（堆调整时，相等元素的相对位置可能改变）；
- 适用场景：大规模数据、对空间要求严格的场景（如嵌入式系统）；缺点是缓存友好性差（堆元素访问不连续）。
8. 计数排序（Counting Sort）——“非比较型线性排序”
基本原理
不依赖元素间的比较，而是通过统计每个元素的出现次数，计算出该元素在有序数组中的 “最终位置”，直接将元素放入对应位置。适用于元素值范围较小且为整数的场景。
执行步骤（升序为例，假设元素值范围为 [min_val, max_val]）
- 统计次数：创建计数数组 count，count [v - min_val] 表示元素 v 的出现次数；
- 计算前缀和：将 count 数组转换为前缀和数组，count [i] 表示 “小于等于（min_val + i）的元素总数”，即元素（min_val + i）的最终位置上限；
- 反向填充：从原数组末尾向前遍历，将当前元素 v 放入有序数组 res 的（count [v - min_val] - 1）位置，同时将 count [v - min_val] 减 1（确保相同元素的相对位置）；
- 将 res 数组复制回原数组，完成排序。
特性
- 时间复杂度：O (n + k)（n 为数据量，k 为元素值范围大小，k≤n 时为 O (n)）；
- 空间复杂度：O (n + k)（需计数数组 count 和结果数组 res）；
- 稳定性：稳定（反向填充时，相同元素按原顺序放入）；
- 适用场景：元素为整数且值范围小的场景（如学生成绩排序：0-100，k=101）、作为基数排序的子排序。
9. 桶排序（Bucket Sort）——“分桶 + 子排序”
基本原理
将元素分配到多个 “桶”（Bucket） 中，每个桶对应一个值范围；对每个非空桶单独执行 “子排序”（如插入排序、快速排序）；最后将所有桶中的元素按顺序合并，得到有序数组。桶的数量和范围需合理设计。
执行步骤（升序为例）
- 确定桶的数量和范围：假设元素值范围为 [min_val, max_val]，桶数为 m，则每个桶的范围为 (max_val - min_val + 1)/m（向上取整）；
- 分配元素：遍历原数组，将每个元素放入对应范围的桶中；
- 子排序：对每个非空桶调用内置排序（如插入排序）；
- 合并桶：将所有桶中的元素按桶的顺序依次取出，拼接为有序数组。
特性
- 时间复杂度：O (n + m * k log k)（m 为桶数，k 为每个桶的平均元素数；若 m≈n 且 k=1，时间复杂度为 O (n)）；
- 空间复杂度：O (n + m)（需存储 m 个桶和 n 个元素）；
- 稳定性：取决于子排序算法（子排序用稳定算法则桶排序稳定）；
- 适用场景：元素值分布均匀的大规模数据（如用户年龄排序：0-120，桶数 12，每个桶对应 10 岁范围）。
10. 基数排序（Radix Sort）——“按位排序”
基本原理
不直接比较元素大小，而是按元素的 “位”（个位、十位、百位...）从低到高（或从高到低）排序，每一位排序都使用 “计数排序” 或 “桶排序” 作为子排序（确保稳定性）。适用于整数或可转换为整数的元素（如字符串、日期）。
执行步骤（升序为例，按低位到高位排序）
- 确定最大位数：找到原数组中最大元素的位数 d（如 123 的位数为 3）；
- 按位排序：对每一位（从第 1 位 “个位” 到第 d 位 “高位”）执行计数排序：
- 提取当前位的数字（如 123 的个位为 3，十位为 2）；
- 以当前位的数字为 “键”，用计数排序对原数组排序（确保稳定性，避免高位排序结果被破坏）；
- 所有位排序完成后，数组完全有序。
特性
- 时间复杂度：O (d * (n + k))（d 为最大位数，k 为每一位的取值范围，如十进制 k=10；d 通常很小，接近 O (n)）；
- 空间复杂度：O (n + k)（子排序需额外空间）；
- 稳定性：稳定（子排序用稳定算法）；
- 适用场景：大规模整数排序（如身份证号、手机号）、字符串排序（按字符 ASCII 码）；缺点是需处理负数（可通过偏移量转换为正数）。
三、常用排序算法特性对比表
| 排序算法 | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 | 核心适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模、几乎有序数据 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 | 小规模、对稳定性无要求 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模、几乎有序数据、链表 |
| 希尔排序 | O(n²) | O(n log n) | O(1) | 不稳定 | 中规模数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模、需稳定性的场景 |
| 快速排序 | O(n²) | O(n log n) | O(log n) | 不稳定 | 大规模、通用场景（工业界首选） |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模、空间严格受限场景 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 | 元素为整数、值范围小（如成绩） |
| 桶排序 | O(n + m*k log k) | O (n)（均匀分布） | O(n + m) | 稳定 | 元素分布均匀的大规模数据 |
| 基数排序 | O(d*(n + k)) | O (n)（d 小） | O(n + k) | 稳定 | 整数、字符串等可按位排序的数据 |
四、排序算法选择建议
- 小规模数据（n≤1000）：优先选择插入排序（效率高于冒泡、选择），或希尔排序（中规模）；
- 大规模数据（n≥10^4）：
- 对稳定性无要求：快速排序（平均最快）、堆排序（空间最优）；
- 对稳定性有要求：归并排序、基数排序（元素可按位处理）；
- 元素值范围小：计数排序（如 0-100 的成绩）；
- 元素分布均匀：桶排序（如年龄、薪资）；
- 链表数据：插入排序（无需移动元素）、归并排序（链表合并无需额外空间）；
- 内存受限场景：堆排序、希尔排序（原地排序）。
通过理解不同排序算法的核心特性和适用场景，可在实际开发中根据数据规模、数据类型和性能需求，选择最优的排序方案。