跳转至

排序简介

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

稳定性

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

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

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

时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系,类似的有空间复杂度,用来描述算法的空间消耗的规模。

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

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

基于比较的排序算法的时间复杂度下限是 O(n\log n)的。

当然也有不是 O(n\log n)的,桶排序的时间复杂度是 O(n),但是它是在「用空间换时间」,它的空间复杂度是 O(所排序的最大数 )

当待排序的关键码序列基本有序时,插入排序最快。


评论