排序算法要素

几种排序算法

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

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

如何分析一个排序算法？

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

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

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

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

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

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