OI-wiki 排序算法总览从稳定性到复杂度的一站式入门指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读排序是算法竞赛OI/ICPC中最基础、最高频的操作之一而理解排序算法是什么、如何衡量其优劣则是掌握全部排序算法冒泡、插入、选择、归并、快速、堆、计数、基数、希尔等的前提。本文以 OI-wiki 的排序算法导论章节为主线系统讲解排序算法的定义、稳定性判定、时间复杂度与空间复杂度分析方法并结合仓库内各排序算法的文档与参考实现给出可直接用于解题实践的选择依据与复杂度对比表。排序算法的定义排序算法英语Sorting algorithm是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样性质也大多不同有的以简单直观见长如冒泡排序、选择排序有的以渐进效率著称如归并排序、快速排序还有的跳出基于比较的框架实现线性时间排序如计数排序、基数排序。从算法抽象的角度看正如 docs/basic/index.md 所述算法是计算的方法使用数学化的描述侧重于思想可以被看作抽象的程序——同一个排序算法可以有许多种不同的实现方式因此本仓库为每个排序算法都提供了多种语言C、Python、Java 等的参考实现。排序算法的性质稳定性稳定性的定义稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。拥有稳定性这一特性的算法会让原本有相等键值的记录维持相对次序。形式化地说如果一个排序算法是稳定的当有两个相等键值的记录 $R$ 和 $S$且在原本的列表中 $R$ 出现在 $S$ 之前那么在排序过的列表中 $R$ 也将会在 $S$ 之前。稳定性并非排序的正确性要求而是一项附加性质。当待排序元素带有多个关键字、需要按主关键字排序后再按次关键字处理时稳定性就显得尤为重要——例如基数排序对每一关键字进行稳定排序其正确性正建立在内层排序稳定这一前提之上。稳定排序一览根据 docs/basic/sort-intro.md以下排序算法是稳定的基数排序只要内层关键字的排序是稳定的MSD 和 LSD 两种基数排序都是稳定的见 docs/basic/radix-sort.md。计数排序在 docs/basic/counting-sort.md 中利用出现次数的前缀和并从右至左放置元素即可保证排序后数组保持原序列中相同 key 值的相对顺序得到一种稳定的排序算法。插入排序逐一向已有序部分插入新元素相等元素插入在已有元素的后面天然稳定。冒泡排序仅在前面的元素与后面的元素满足给定排序条件即严格逆序时才交换相等的元素不会被交换因此稳定。参考 docs/basic/bubble-sort.md 的伪代码if A[i] A[i 1]使用的是严格大于这正是稳定性的来源。归并排序稳定性体现在合并过程——为保证稳定前段首元素小于等于后段首元素时而非小于时就要作为最小值放入结果数组。在 docs/basic/merge-sort.md 的merge实现中代码先判断b[j] a[i]等价地保证了相等时优先取前段元素从而维持稳定。不稳定排序一览以下排序算法是不稳定的选择排序稳定性取决于具体实现。若用链表实现任意位置插入删除均为 $O(1)$可保证稳定但 OI 中常见的数组实现只能通过swap将未排序部分的最小元素交换到已排序部分交换操作会破坏相等元素的相对顺序因此数组实现的选择排序不稳定详见 docs/basic/selection-sort.md。堆排序本质是建立在堆上的选择排序同样因交换位置的操作而不稳定见 docs/basic/heap-sort.md。快速排序分区交换的过程会跨元素交换是一种不稳定的排序算法见 docs/basic/quick-sort.md。希尔排序对不相邻的记录进行比较和移动间隔插入跨距交换破坏了稳定性见 docs/basic/shell-sort.md。小技巧当题目要求稳定排序时优先考虑归并排序或计数排序若在 C 中需要库函数稳定排序可使用std::stable_sort见 docs/basic/stl-sort.md它在额外内存可用时时间复杂度为 $O(n\log n)$。排序算法的时间复杂度时间复杂度的含义与计算时间复杂度用来衡量一个算法的运行时间和输入规模的关系通常用 $O$ 表示。简单计算复杂度的方法一般是统计简单操作的执行次数有时候也可以直接数循环的层数来近似估计。更严谨地讲在 docs/basic/complexity.md 中我们关心的是算法用时随数据规模增长的趋势并使用渐近符号形式化描述大 $O$ 符号给出渐近上界$f(n)O(g(n))$ 当且仅当 $\exists c,n_0$ 使得 $\forall n \ge n_0, 0\le f(n)\le c\cdot g(n)$$\Theta$ 符号同时给出上下界$\Omega$ 符号描述渐近下界。最优、平均与最坏时间复杂度时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。算法的运行用时不仅由输入规模决定还与输入内容相关因此最坏时间复杂度每个输入规模下用时最长的输入对应的时间复杂度平均期望时间复杂度每个输入规模下所有可能输入对应用时的平均值的复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度因为它代表的是算法运行水平的下界在评测中不会出现更差的结果了。例如快速排序的最优与平均时间复杂度为 $O(n\log n)$但在每次选择的分界值都是序列最值的退化情况下最坏时间复杂度为 $O(n^2)$——因此竞赛选手必须意识到朴素快速排序存在被毒瘤数据卡成 $O(n^2)$ 的风险参考 docs/basic/quick-sort.md 中的优化讨论。基于比较的排序下限$O(n\log n)$基于比较的排序算法的时间复杂度下限是 $O(n\log n)$。这意味着任何只通过两两比较来确定元素顺序的排序算法在最坏情况下都不可能突破 $\Theta(n\log n)$。归并排序最优、最坏、平均均为 $\Theta(n\log n)$、堆排序三种情况均为 $O(n\log n)$都达到了这个下界。超越下界非比较排序当然也有不是 $O(n\log n)$ 的排序算法它们通过利用输入数据的额外信息如值域绕过比较下界计数排序的时间复杂度是 $O(nw)$其中 $w$ 代表输入数据的值域大小。其参考实现见 docs/basic/code/counting-sort/counting-sort_1.cpp先用cnt数组统计每个值出现的次数再对cnt求前缀和最后从右至左将元素放置到正确位置。基数排序将元素拆分为 $k$ 个关键字逐一稳定排序。若每个关键字的值域都不大可用计数排序作为内层排序此时复杂度为 $O(kn\sum_{i1}^k w_i)$其中 $w_i$ 为第 $i$ 关键字的值域大小见 docs/basic/radix-sort.md。各排序算法复杂度对比以下是本仓库 docs/basic/sort-intro.md 及对应算法章节归纳出的常用排序算法复杂度对比排序算法最优时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性参考章节冒泡排序$O(n)$$O(n^2)$$O(n^2)$$O(1)$稳定bubble-sort.md插入排序$O(n)$$O(n^2)$$O(n^2)$$O(1)$稳定insertion-sort.md选择排序$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$不稳定数组实现selection-sort.md希尔排序$O(n)$取决于间距序列经典选取可达 $O(n^{3/2})$ / $O(n\log^2 n)$$o(n^2)$经典间距序列$O(1)$不稳定shell-sort.md归并排序$\Theta(n\log n)$$\Theta(n\log n)$$\Theta(n\log n)$$\Theta(n)$稳定merge-sort.md堆排序$O(n\log n)$$O(n\log n)$$O(n\log n)$$O(1)$原地不稳定heap-sort.md快速排序$O(n\log n)$$O(n\log n)$$O(n^2)$$O(\log n)$递归栈不稳定quick-sort.md计数排序$O(nw)$$O(nw)$$O(nw)$$O(w)$稳定counting-sort.md基数排序$O(kn\sum w_i)$$O(kn\sum w_i)$$O(kn\sum w_i)$$O(kn)$稳定radix-sort.md注各算法的时间/空间复杂度结论均取自对应文档的性质小节如 docs/basic/heap-sort.md 明确堆排序由于可以在输入数组上建立堆是一个原地算法。上图docs/basic/images/sort-intro-1.apng直观展示了多种排序算法在同一组数据上的执行过程与效率差异可作为理解复杂度差异的辅助材料。排序算法的空间复杂度与时间复杂度类似空间复杂度用来描述算法空间消耗的规模。一般来说空间复杂度越小算法越好——尤其在内存限制严格的 OI 题目中空间开销往往与时间效率同等重要。各算法的空间消耗差异很大原地算法堆排序可以在输入数组上直接建立二叉堆空间复杂度 $O(1)$是典型的原地算法希尔排序的空间复杂度同样为 $O(1)$。线性辅助空间归并排序的空间复杂度为 $\Theta(n)$可只使用 $\Theta(1)$ 辅助空间但为便捷通常使用与原数组等长的辅助数组基数排序的 MSD 与 LSD 实现空间复杂度均为 $O(kn)$。值域相关空间计数排序需要额外的计数数组空间复杂度为 $O(w)$当值域 $w$ 远大于 $n$ 时空间代价不容忽视。空间复杂度随输入规模变化的趋势同样可以用 docs/basic/complexity.md 中的渐近符号来描述。竞赛场景下的选择策略综合上述性质在 OI 解题中可以按以下思路快速选定排序方案数据规模大$n$ 达 $10^5\sim10^6$ 级优先使用 $O(n\log n)$ 的排序。C 中直接使用std::sort现代标准库实现为内省排序最坏时间复杂度 $O(n\log n)$详见 docs/basic/stl-sort.md是最省心的选择需要稳定排序时改用std::stable_sort。数据规模小如 $n\le 10^3$冒泡、插入、选择等 $O(n^2)$ 的简单排序完全可行且代码量小、不易出错。值域小$w$ 与 $n$ 同阶计数排序可做到 $O(nw)$ 的线性时间且实现稳定参考 docs/basic/counting-sort.md。数据可拆分为多个关键字如整数按位、字符串按字典序基数排序MSD 或 LSD通常优于基于比较的排序尤其在对字符串排序时优势明显字符串比较本身可能达到 $O(n)$见 docs/basic/radix-sort.md。需要求第 $k$ 大元素而非完整排序可使用std::nth_element平均 $O(n)$或在 docs/basic/quick-sort.md 的线性找第 k 大的数一节中基于快速排序的划分思想实现。深入阅读复杂度分析渐近符号$O$、$\Omega$、$\Theta$、$o$、$\omega$的形式化定义、主定理与均摊复杂度的完整讲解各排序算法详解冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序、希尔排序、计数排序、基数排序、桶排序、锦标赛排序、排序应用标准库排序函数qsort、std::sort、std::nth_element、std::stable_sort、std::partial_sort的用法与自定义比较规则严格弱序注意事项各排序算法的参考代码统一存放在 docs/basic/code 目录下对应的输入输出样例位于 docs/basic/examples 目录可结合样例自行验证算法行为。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考