Appearance
排序
常用的排序算法有:
排序算法 | 时间复杂度 | 是否基于比较 |
---|---|---|
冒泡、插入、选择 | O(n^2) | 是 |
快排、归并 | o(nlogn) | 是 |
桶、计数、基数 | O(n) | 否 |
如何分析一个算法
学习排序算法,除了要知道它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法应该要考虑以下几个方面
排序算法的执行效率
对于排序算法,需要从以下几点来衡量
- 最好情况、最坏情况、平均时间复杂度:为什么要区分这三种复杂度呢?第一,有些排序算法会区分,为了好对比,所以最好都做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。。
- 时间复杂度的系数、常数、低阶:时间复杂度反应的是执行时间随着数据规模增长的变化趋势,但是实际的开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,对于同一阶时间复杂度的排序算法的性能对比,就需要把系数、常数、低阶考虑进来。
- 比较次数和交换(或移动)次数:对于基于比较的排序算法,会涉及两种操作,一种是元素比较大小,另一种是交换(或移动),所以分析执行效率的时候,应该把比较次数和交换(或移动次数)也考虑进来。
排序算法的内存消耗
内存消耗可以通过空间复杂度来衡量。这里还引入一个概念,原地排序。原地排序算法,特指空间复杂度为 O(1) 的排序算法。冒泡、插入、选择都属于原地排序。
排序算法的稳定性
针对排序算法还有一个重要的度量指标,稳定性。就是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序顺序不变。
例如,一组数据 2,3,4,2,按照大小排序之后就是 2,2,3,4。
这里边有两个 2,经过某种排序算法排序之后,如果两个 2 的前后顺序没有变化,那么就把这种算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。