排序简介 - OI Wiki

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序 ... 外部链接¶. 排序算法- 维基百科，自由的百科全书 ... 跳转至简介比赛相关工具软件语言基础算法基础搜索动态规划字符串数学数据结构图论计算几何杂项专题关于HuluschoolOIWikiOI-wiki/OI-wiki简介简介GettingStarted关于本项目如何参与格式手册F.A.Q.用Docker部署OIWiki镜像站列表致谢比赛相关比赛相关比赛相关简介赛事赛事OI赛事与赛制ICPC/CCPC赛事与赛制题型题型题型概述交互题学习路线学习资源技巧技巧读入、输出优化常见错误常见技巧出题工具软件工具软件工具软件简介代码编辑工具代码编辑工具VimEmacsVSCodeAtomEclipseNotepad++KateDev-C++GeanyXcodeGUIDESublimeText评测工具评测工具评测工具简介ArbiterCenaCCRPlusLemon命令行WSL(Windows10)SpecialJudgeTestlibTestlibTestlib简介通用GeneratorValidatorInteractorCheckerPolygonOJ工具LaTeX入门Git语言基础语言基础语言基础简介C++基础C++基础Hello,World!C++语法基础变量运算流程控制语句流程控制语句分支循环高级数据类型高级数据类型数组结构体指针函数文件操作C++标准库C++标准库C++标准库简介STL容器STL容器STL容器简介迭代器序列式容器关联式容器无序关联式容器容器适配器STL算法bitsetstringpairC++进阶C++进阶类命名空间值类别重载运算符引用常值新版C++特性Lambda表达式pb_dspb_dspb_ds简介堆平衡树C与C++区别Pascal转C++急救Python速成Java速成算法基础算法基础算法基础简介复杂度枚举模拟递归&分治贪心排序排序排序简介排序简介目录简介性质稳定性时间复杂度空间复杂度外部链接评论选择排序冒泡排序插入排序计数排序基数排序快速排序归并排序堆排序桶排序希尔排序锦标赛排序排序相关STL排序应用前缀和&差分二分倍增构造搜索搜索搜索部分简介DFS（搜索）BFS（搜索）双向搜索启发式搜索A*迭代加深搜索IDA*回溯法DancingLinksAlpha-Beta剪枝优化动态规划动态规划动态规划部分简介动态规划基础记忆化搜索背包DP区间DPDAG上的DP树形DP状压DP数位DP插头DP计数DP动态DP概率DPDP优化DP优化单调队列/单调栈优化斜率优化四边形不等式优化状态设计优化其它DP方法字符串字符串字符串部分简介字符串基础标准库字符串匹配字符串哈希字典树(Trie)前缀函数与KMP算法Boyer-Moore算法Z函数（扩展KMP）自动机AC自动机后缀数组(SA)后缀数组(SA)后缀数组简介最优原地后缀排序算法后缀自动机(SAM)后缀平衡树广义后缀自动机后缀树Manacher回文树序列自动机最小表示法Lyndon分解Main-Lorentz算法数学数学数学部分简介符号复数位运算快速幂进位制高精度计算平衡三进制数论数论数论基础素数最大公约数数论分块欧拉函数筛法Meissel-Lehmer算法分解质因数裴蜀定理类欧几里德算法欧拉定理&费马小定理乘法逆元线性同余方程中国剩余定理威尔逊定理升幂定理卢卡斯定理二次剩余拉格朗日定理原根BSGS莫比乌斯反演杜教筛PowerfulNumber筛Min_25筛洲阁筛连分数Stern-Brocot树与Farey序列Pell方程多项式多项式多项式部分简介代数基本定理拉格朗日插值快速傅里叶变换快速数论变换快速复数论变换快速沃尔什变换ChirpZ变换多项式求逆多项式开方多项式除法|取模多项式对数函数|指数函数多项式牛顿迭代多项式多点求值|快速插值多项式三角函数多项式反三角函数常系数齐次线性递推多项式平移|连续点值平移生成函数生成函数生成函数简介符号化方法普通生成函数指数生成函数狄利克雷生成函数线性代数线性代数向量矩阵高斯消元特征多项式线性基线性规划线性规划线性规划简介单纯形算法组合数学组合数学排列组合卡特兰数斯特林数贝尔数伯努利数康托展开容斥原理抽屉原理EulerianNumber分拆数群论群论群论简介置换群概率初步斐波那契数列博弈论博弈论博弈论简介公平组合游戏非公平组合游戏反常游戏牛顿迭代法数值积分分段打表傅里叶-莫茨金消元法序理论杨氏矩阵Schreier–Sims算法Berlekamp-Massey算法数据结构数据结构数据结构部分简介栈队列链表哈希表并查集并查集并查集并查集复杂度堆堆堆简介二叉堆配对堆左偏树块状数据结构块状数据结构分块思想块状数组块状链表树分块SqrtTree单调栈单调队列ST表树状数组线段树李超线段树区间最值操作&区间历史最值划分树二叉搜索树&平衡树二叉搜索树&平衡树二叉搜索树简介TreapSplayWBLTSizeBalancedTreeAVL树替罪羊树笛卡尔树左偏红黑树跳表可持久化数据结构可持久化数据结构可持久化数据结构简介可持久化线段树可持久化块状数组可持久化平衡树可持久化字典树可持久化可并堆树套树树套树线段树套线段树平衡树套线段树线段树套平衡树树状数组套主席树分块套树状数组K-DTree珂朵莉树动态树动态树LinkCutTreeEulerTourTreeTopTree析合树PQ树手指树霍夫曼树图论图论图论部分简介图论相关概念图的存储DFS（图论）BFS（图论）树上问题树上问题树基础树的直径最近公共祖先树的重心树链剖分树上启发式合并虚树树分治动态树分治AHU算法树哈希矩阵树定理有向无环图拓扑排序最小生成树斯坦纳树最小树形图最小直径生成树最短路拆点差分约束k短路同余最短路连通性相关连通性相关强连通分量双连通分量割点和桥圆方树2-SAT欧拉图哈密顿图二分图最小环平面图图的着色网络流网络流网络流简介最大流最小割费用流上下界网络流Stoer-Wagner算法图的匹配图的匹配图匹配增广路二分图最大匹配二分图最大权匹配一般图最大匹配一般图最大权匹配Prufer序列LGV引理弦图计算几何计算几何计算几何部分简介二维计算几何基础三维计算几何基础极坐标系距离Pick定理三角剖分凸包扫描线旋转卡壳半平面交平面最近点对随机增量法反演变换计算几何杂项杂项杂项杂项简介离散化双指针离线算法离线算法离线算法简介CDQ分治整体二分莫队算法莫队算法莫队算法简介普通莫队算法带修改莫队树上莫队回滚莫队莫队配合bitset分数规划随机化随机化随机函数随机化技巧爬山算法模拟退火悬线法计算理论基础字节顺序约瑟夫问题格雷码表达式求值在一台机器上规划任务主元素问题Garsia-Wachs算法15-puzzleKahan求和专题专题RMQ并查集应用括号序列关于Hulu关于Hulu关于Hulu目录简介性质稳定性时间复杂度空间复杂度外部链接评论排序简介本页面将简要介绍排序算法。

简介¶排序算法（英语：Sortingalgorithm）是一种将一组特定的数据按某种顺序进行排列的算法。

排序算法多种多样，性质也大多不同。

性质¶稳定性¶稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录和，且在原本的列表中出现在之前，在排序过的列表中也将会是在之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序不是稳定排序。

时间复杂度¶主页面：复杂度时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用表示。

简单计算复杂度的方法一般是统计“简单操作”的执行次数，有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。

OI竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。

基于比较的排序算法的时间复杂度下限是的。

当然也有不是的。

例如，计数排序的时间复杂度是，其中代表输入数据的值域大小。

以下是几种排序算法的比较。

空间复杂度¶与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。

一般来说，空间复杂度越小，算法越好。

外部链接¶排序算法-维基百科，自由的百科全书build本页面最近更新：2021/8/1117:09:32，更新历史edit发现错误？想一起完善？在GitHub上编辑此页！people本页面贡献者：NachtgeistW,Backl1ght,Alisahhh,Enter-tainer,Great-designer,llh721113,ouuan,partychickencopyright本页面的全部内容在CCBY-SA4.0和SATA协议之条款下提供，附加条款亦可能应用评论