排序算法要素

几种排序算法

.

还有希尔排序,堆排序等。

当然还有其他冷门排序:猴子排序,睡眠排序,面条排序。

如何分析一个排序算法?

1. 排序算法的执行效率—— 时间复杂度要更精细

  • 最好情况、最坏情况、平均时间复杂度,为什么要分析这么多种呢?因为数据的不同,算法的执行效果也不同。例如有点数据完全无序,有的数据接近有序。
  • 时间复杂度的系数、常数、低阶。我们知道,我们之前分析复杂度的时候,会忽略这 3 个元素,只需要知道 n 的趋势即可。但在实际的开发中,数据量可能很小,所以,之前忽略的这些常数,低阶,系数,我们也要考虑进去,这样就能进行更精确的对比。
  • 比较次数和交换(移动)次数,大部分排序算法基于比较和交换,我们分析排序算法效率 的时候,应该把比较次数和交换次数也考虑进去。

2. 排序算法的内存消耗—— 原地排序的重要性

  • 算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外,不过,针对排序算法的空间复杂度,我们通常有个 “原地排序” 的概念,表示 O1 空间复杂度——所谓原地排序算法。

3. 排序算法的稳定性—— 相等的数据前后位置不变

  • 仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的,针对排序算法,一个重要的指标是“稳定性”。
    即如果待排序中的序列中存在值相同的元素,经过排序之后,相等元素之间的先后顺序不变。例子:一组数据有 时间戳属性 和 价格属性,我们需要既按照时间戳排序,又按照价格排序。我们可以先按照时间戳进行排序,然后按照价格进行排序。注意:如果价格相同,顺序不能变,否则时间戳就不对了!这就是排序算法稳定的重要性。

排序算法要素
http://thinkinjava.cn/2019/10/19/2019/1019-sort-algorithm/
作者
莫那·鲁道
发布于
2019年10月19日
许可协议