2.5 应用

一 将各种数据排序

1.1 交易事务

商业数据处理

1.2 指针排序

C和C++中，需要明确地指出操作的是数据还是指向数据的指针，而在Java中，指针操作是隐式的。除了原始数据类型之外，我们操作的总是数据的引用（指针）。

1.3 不可变的键

例String、Integer、Double和File都是不可变的。

1.4 廉价的交换

1.5 多种排序方法

Java的Comparator接口允许我们在一个类中实现多种排序方法。

1.6 多键数组

Comparator接口

1.7 使用比较器实现优先队列

1.8 稳定性

稳定的（插入排序和归并排序）

不稳定（选择排序、希尔排序、快速排序和堆排序）

有很多办法能够将任意排序算法变成稳定的。

有时候稳定性没有必要，而且维持稳定性需要用大量额外的时间和空间。

二 我应该使用哪种排序算法

如果稳定性很重要而空间又不是问题，归并排序可能是最好的。

2.1 将原始类型数据排序

一些性能优先的应用可能是将数字排序，因此更合理的做法是跳过引用直接将原始数据类型的数据排序。

2.2 Java系统库的排序算法

java.util.Arrays.sort()

三 问题的归约

3.1 找出重复元素

3.2 排名

3.3 优先队列

3.4 中位数与顺序统计