排序简介
排序算法多种多样 ，性质也大多不同。
稳定性¶
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
选择排序、堆排序、快速排序不是稳定排序。
时间复杂度¶
时间复杂度用来衡量一个算法的运行时间和输入规模的关系，类似的有空间复杂度，用来描述算法的空间消耗的规模。
简单计算复杂度的方法一般是统计“简单操作”的执行次数，有时候也可以直接数循环的层数来近似估计。
时间复杂度分为最坏时间复杂度、平均时间复杂度、最好时间复杂度等等。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。
基于比较的排序算法的时间复杂度下限是 O(n\log n) 的。
当然也有不是 O(n\log n) 的，计数排序的时间复杂度是 O(n+w) ，其中 w 代表输入数据的值域大小。
当待排序的关键码序列基本有序时，插入排序最快。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用