排序 #

常用的排序算法有：

如何分析一个算法 #

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

排序算法的执行效率 #

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

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

排序算法的内存消耗 #

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

排序算法的稳定性 #

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

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

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