算法第四版 —— 排序算法应用

排序有用的一个主要原因是，在一个有序的数组中查找一个元素要比在一个无序的数组中查找简单得多。

1 应该使用哪种排序算法

插入排序的效率取决于输入元素的排列情况。

快速排序的运行效率由概率提供保证。三向快速排序的运行效率由概率保证，同时也取决于输入元素的分布情况。

快速排序是最快的通用排序算法。在大多数实际情况中，快速排序是最佳选择。

1.1 Java 系统库的排序算法

Java 系统库的排序方法 java.util.Arrays.sort() 根据不同的参数类型，代表了一系列的排序算法：

• 每种原始数据类型都有一个不同的排序方法；
• 一个适用于所有实现了 Comparable 接口的数据类型的排序方法；
• 一个适用于实现了比较器 Comparator 的数据类型的排序方法。

对于原始数据类型，系统库使用三向切分的快速排序，牺牲稳定性换取速度和空间；对引用类型使用归并排序，牺牲速度和空间换取稳定性。

2 问题的归约

归约指的是为解决某个问题而发明的算法正好可以用来解决另一种问题。每次用解决问题 B 的方法来解决问题 A 时，就是在将 A 归约为 B。

很多问题的第一想法往往是平方级别的暴力破解。但很多情况下如果先将数据排序，那么解决剩下的问题之需要线性级别的时间了。

以下问题可以归约为排序：

• 找出重复元素，可以先排序后再遍历数组；
• 排列、排名问题，比如计算两个排列之间的 Kendall tau 距离；
• 归约为优先队列，找到输入流中 M 个最大元素，或者将 M 个有序输入流合并为一个有序输入流；
• 查找一组元素的中位数，可以归约为找到一组数的第 k 小的元素，并使用快速排序的 partition 解决。