算法自学笔记：系统排序

排序算法在程序开发中有大量应用。有时是直接使用，如对音乐播单里的歌曲进行排序，有时是使用排序简化问题，如convex hull 问题中使用排序优化比暴力求解快很多，而有时是不明显的应用。

java语言提供了封装好的排序方法 Arrays.sort() 该方法接受基础数据类型和实现Comparable 或 Comparator的对象。其参数为要进行排序的数组，也可以加上指定的Comparator 该方法对于基础数据类型使用快速排序以提高速度，而对于对象进行归并排序以保证稳定性和保证nlogn时间下限。

三向切分快速排序被广泛用于C C++ java等多个语言内部封装的排序方法，这一排序法包括三向切分（和之前我们讲的狄克斯特拉三向切分差不多），不过这一方法选择基准值，避免时间复杂度提示为nlogn的方法不是通过把输入数组随机打乱，而是使用一个叫Tukey’s ninther的方法。

Tukey’s ninther方法首先在原数组里随机抽9个元素，并分成3组，取每一组的中位数元素。然后再取这三个中位数的中位数作为基准值。这样抽样可以保证得到的基准值位于数组中位数左右。这样相对于直接打乱可以节省一定时间，因为打乱数组，如使用Knuth’s shuffle， 需要遍历整个数组，而Tukey’s ninther只需要进行12次选取。

但是java系统排序也不是完全没有漏洞的，一些极端输入（在网课附件里有一个例子）会导致时间复杂度提升，这主要是Tukey’s ninther导致的失误，因而完全打乱数组才能保证百分比无差错。另外，如果数据量过大可能导致栈溢出（快速排序和归并排序依靠递归）。

现在已有的排序算法可能有上百种，除了常规对时间复杂度和空间复杂度的比较，选取合适的排序算法一般还会有以下考虑：
1 稳定性
2 出现较多相同键时的性能
3 最糟时间复杂度
4 对输入依赖
没有排序算法是完美的，而系统提供排序算法一般可以解决大多数情况

对之前介绍的排序算法比较