Skip to content
On this page

排序

常用的排序算法有:

排序算法时间复杂度是否基于比较
冒泡、插入、选择O(n^2)
快排、归并o(nlogn)
桶、计数、基数O(n)

如何分析一个算法

学习排序算法,除了要知道它的算法原理、代码实现之外,更重要的是要学会如何评价、分析一个排序算法。分析一个排序算法应该要考虑以下几个方面

排序算法的执行效率

对于排序算法,需要从以下几点来衡量

  1. 最好情况、最坏情况、平均时间复杂度:为什么要区分这三种复杂度呢?第一,有些排序算法会区分,为了好对比,所以最好都做一下区分。第二,对于要排序的数据,有的接近有序,有的完全无序。有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。。
  2. 时间复杂度的系数、常数、低阶:时间复杂度反应的是执行时间随着数据规模增长的变化趋势,但是实际的开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,对于同一阶时间复杂度的排序算法的性能对比,就需要把系数、常数、低阶考虑进来。
  3. 比较次数和交换(或移动)次数:对于基于比较的排序算法,会涉及两种操作,一种是元素比较大小,另一种是交换(或移动),所以分析执行效率的时候,应该把比较次数和交换(或移动次数)也考虑进来。

排序算法的内存消耗

内存消耗可以通过空间复杂度来衡量。这里还引入一个概念,原地排序。原地排序算法,特指空间复杂度为 O(1) 的排序算法。冒泡、插入、选择都属于原地排序。

排序算法的稳定性

针对排序算法还有一个重要的度量指标,稳定性。就是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序顺序不变。

例如,一组数据 2,3,4,2,按照大小排序之后就是 2,2,3,4。

这里边有两个 2,经过某种排序算法排序之后,如果两个 2 的前后顺序没有变化,那么就把这种算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法

排序 has loaded