如何分析排序算法

分析方法

对于排序算法执行效率的分析，不仅仅只是简简单单的一个时间复杂度。

还需要从以下方面进行分析：

在算法中，内存消耗基本上通过空间复杂度来衡量。

但是，在排序算法中，会有一个新的概念用来衡量内存消耗，即原地排序。原地排序算法特指不需要另外空间存储的排序算法，空间复杂度能达到 $O (1)$ 。

针对排序算法，还有稳定性这样一个重要的度量指标。

这个概念是指，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

常见的排序算法有很多，这里列出 10 种排序算法作比较。而这 10 种常见的排序算法会根据是否进行比较分为两种：

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	$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_{2} n)$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (1)$	不稳定
快速排序	$O (n \log_{2} n)$	$O (n^{2})$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	不稳定
归并排序	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$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 的 qsort() 函数，数据量较小时会优先使用归并排序算法来对输入数据排序，当数据量比较大时，qsort() 会改用快速排序算法来排序。

在归并排序中，每个元素小于 32 时，会直接进行归并排序；当有元素大于 32 时，则先将元素的指针拷贝到临时空间，再使用归并排序对指针进行排序。

在快排过程中，元素个数小于等于 4 个时候，会使用插入排序代替快速排序。

例如 JDK 8 中 Arrays.sort() 的底层实现，也根据不同的情况使用到多种排序算法。

对于元素个数小于 47 的序列，使用的是插入排序算法；对于元素个数大于 47 而小于 286 的序列，使用的则是快速排序算法。

而对于超过 286 个元素的序列，还会判断这个序列是否结构化（数据是否时升时降），结构化的序列会使用归并排序算法，而非结构化的序列仍然会使用快速排序算法。