分析方法
执行效率
还需要从以下方面进行分析：
最好情况、最坏情况、平均情况时间复杂度。对于排序算法来说，有序度不同的数据，对于排序的执行时间有一定的影响，从多个方面分析时间复杂度会更加准确
时间复杂度的系数、常数、低阶。在实际开发中，大多是对一些规模较小的数据进行排序，实际运行速度是非常快的，这时候也可以把系数、常数、低阶考虑进来
比较次数或交换（移动）次数。常见的排序算法都是基于比较的，这时候会涉及到元素比较大小和元素交换或移动，这时候比较次数和交换次数也会影响到执行效率
内存消耗
但是，在排序算法中，会有一个新的概念用来衡量内存消耗，即原地排序。原地排序算法特指不需要另外空间存储的排序算法，空间复杂度能达到 \(O(1\。
稳定性
这个概念是指，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
常见排序算法
比较类排序：冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序
非比较排序：计数排序、桶排序、基数排序
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | \(O(n^2\ | \(O(n^2\ | \(O(n\ | \(O(1\ | 稳定 |
| 选择排序 | \(O(n^2\ | \(O(n^2\ | \(O(n^2\ | \(O(1\ | 不稳定 |
| 插入排序 | \(O(n^2\ | \(O(n^2\ | \(O(n\ | \(O(1\ | 稳定 |
| 希尔排序 | \(O(n^{1.3 \sim 2}\ | \(O(n^2\ | \(O(n\ | \(O(1\ | 不稳定 |
| 堆排序 | \(O(n\log_2n\ | \(O(n\log_2n\ | \(O(n\log_2n\ | \(O(1\ | 不稳定 |
| 快速排序 | \(O(n\log_2n\ | \(O(n^2\ | \(O(n\log_2n\ | \(O(n\log_2n\ | 不稳定 |
| 归并排序 | \(O(n\log_2n\ | \(O(n\log_2n\ | \(O(n\log_2n\ | \(O(n\ | 稳定 |
| 计数排序 | \(O(n+k\ | \(O(n+k\ | \(O(n+k\ | \(O(n+k\ | 稳定 |
| 桶排序 | \(O(n+k\ | \(O(n^2\ | \(O(n\ | \(O(n+k\ | 稳定 |
| 基数排序 | \(O(n \times k\ | \(O(n \times k\ | \(O(n \times k\ | \(O(n+k\ | 稳定 |
如何选择合适的排序算法？
选择依据
在实际开发的时候，并不是时间复杂度低的排序算法就能适用于任何场景。
一般来说，对于小规模的数据进行排序时，可以选择时间复杂度是 \(O(n^2\ 的排序算法；对于大规模的数据进行排序时，需要选择时间复杂度是 \(O(n \log n\ 的排序算法；对于非比较类排序算法，主要应用于特定的场景。
\(O(n^2\ 的排序算法会比 \(O(n \log n\ 的排序算法的效率低，一般指的都是时间复杂度在没有系数、常数、低阶介入比较的情况，当真正使用的时候，这些是不可避免的。
\(O(n^2\ 的排序算法也会比 \(O(n \log n\ 的排序算法的效率高。
排序实现 - Glibc
例如 Glibc 的 函数，数据量较小时会优先使用归并排序算法来对输入数据排序，当数据量比较大时， 会改用快速排序算法来排序。
在快排过程中，元素个数小于等于 4 个时候，会使用插入排序代替快速排序。
排序实现 - Java
对于元素个数小于 47 的序列，使用的是插入排序算法；对于元素个数大于 47 而小于 286 的序列，使用的则是快速排序算法。
而对于超过 286 个元素的序列，还会判断这个序列是否结构化（数据是否时升时降），结构化的序列会使用归并排序算法，而非结构化的序列仍然会使用快速排序算法。