5.7.2 堆排序
我们可以把任意优先队列变成一种排序方法。 将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次插人排序。用基于堆的优先队列这样做等同于哪种排序? 一种全新的排序方法!下面我们就用堆来实现一种经典而优雅的排序算法——堆排序。
堆排序可以分为两个阶段。 在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中; 然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。为了和我们已经学习过的代码保持一致，我们将使用一个面向最大元索的优先队列并重复删除最大元素。为了排序的需要，我们不再将优先队列的具体表示隐藏，并将直接使用swim()和sink()操作。这样我们在排序时就可以将需要排序的数组本身作为堆，因此无需任何额外空间。
5.7.2.1 堆的构造
由N个给定的元素构造一个堆有多难?我们当然可以在与MogN成正比的时间内完成这项任务，只需从左至右遍历数组，用swim(保证扫描指针左侧的所有元素已经是一棵堆有序的完全树即可，就像连续向优先队列中插入元素一样。一个更聪明更高效的办法是从右至左用sink()函数构造子堆。数组的每个位置都已经是一个 子堆的根结点了，sin()对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了，那么在该结点上调用sink()可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆。最后我们在位置1上调用sink()方法，扫描结束。在排序的第一阶段，堆的构造方法和我们的想象有所不同，因为我们的目标是构造一个堆有序的数组并使最 大元素位于数组的开头(次大的元素在附近)而非构造函数结束的末尾。
命题R：用下沉操作由N个元素构造堆只需少于2N次比较以及少于N次交换。
证明：观察可知，构造过程中处理的堆都较小。例如，要构造一个127个元素的堆，我们会处理32个大小为3的堆，16个大小为7的堆，8个大小为15的堆，4个大小为31的堆，2个大小为63的堆和1个大小为127的堆，因此(最坏情况下)需要32X1+ 16x2+8X3+4X4+2x5+1x6=120次交换(两倍于比较)。
算法 堆排序
public static voidsort(Comparable[] a){
int N = a.length;
for(int k=N/2; k>=1; k--){
sink(a,k,N);
}
while(k>1){
exch(a,1,N--);
sink(a,1,N);
}
}
这段代码用sink()方法将a[1]到a[N] 的元素排序sink()被修改过，以a[]和N作为参数)。for 循环构造了堆，然后while循环将最大的元素a[1]和a[N]交换并修复了堆，如此重复直到堆变空。将exch()和less()的实现中的索引减一即可得到和其他排序算法一致的实现(将a[0]至a[N-1]排序)。
5.2.7.2 下沉排序
堆排序的主要 工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。这个过程和选择排序有些类似(按照降序而非升序取出所有元素)，但所需的比较要少得多，因为堆提供了一种从未排序部分找到最大元素的有效方法。
命题S：将N个元素排序，堆排序只衢少于(2NgN+2N)次比较(以及一半次数的交换)。
证明：2N项来自于堆的构造(见命题R)2NgN项来自于每次下沉操作最大可能需要2lgN次比较(见命题P与命题Q)。
5.2.7.3 先下沉后上浮
大多数在 下沉排序期间重新插入堆的元素会被直接加入到堆底。我们可以通过免去检查元素是否到达正确位置来节省时间。在下沉中总是直接提升较大的子结点直至到达堆底，然后再使元素上浮到正确的位置。这个想法几乎可以将比较次数减少一半——接近 了归并排序所需的比较次数(随机数组)。这种方法需要额外的空间，因此在实际应用中只有当比较操作代价较高时才有用(例如，当我们在将字符串或者其他键值较长类型的元素进行排序时)。
堆排序在排序复杂性的研究中有着重要的地位,因为它是我们所知的唯一能够同时最优地利用空间和时间的方法一在 最坏的情况下它也能保证使用一2MgN次比较和恒定的额外空间。当空间十分紧张的时候(例如在嵌入式系统或低成本的移动设备中)它很流行，因为它只用几行就能实现(甚至机器码也是)较好的性能。但现代系统的许多应用很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序、归并排序，甚至是希尔排序。
5.8 应用
排序算法和优先队列在许多场景中有着广泛的应用。研究如何能让我们已经学习过的高效算法在这些应用中大展身手，然后讨论一下应该如何使用我们的排序和优先队列的代码。
排序如此有用的一个主要原因是，在一个有序的数组中查找一个元素 要比在一个 无序的数组中查找简单得多。人们用了一个多世纪发现在一本按姓氏排序的电话黄页中查找某个人的电话号码最容易。现在，数字音乐作家们将歌曲文件按照作家名或是歌曲名排序，搜索引擎按照搜索结果的重要性的高低显示结果，电子表格按照某一列的排序结果显示所有栏，矩阵处理工具将一个对称矩阵的真实特征值按照降序排列，等等。只要队列是有序的，很多其他任务也更容易完成，比如在本书最后的有序索引中查找某项，或是从一列长长的邮件列表或者投票人列表或者网站列表中删去重复项，或是在统计学计算中剔除异常值、查找中位数或者计算比例。
在许多看似无关的领域中， 排序其实仍然是一个重要的子问题。数据压缩、计算机图形学、计算生物学、供应链管理、组合优化、社会选择和投票等，不一而足。通用排序算法是最重要的，因此我们首先会考虑一些在构建适用于 多种情况的排序算法时需要注意的实际问题。虽然部分话题只适用于Java,但每个问题都仍然是所有系统需要解决的。
5.8.1 将各种数据排序
我们的实现的排序对象是由实现了Comparable接口的对象组成的数组。Java 的约定使得我们能够利用Java的回调机制将任意实现了Comparable接口的数据类型排序。实现Comparable接口只需要定义一个compareTo()函数并在其中定义该数据类型中的大小关系。我们的代码直接能够将String、Integer. Double和一些 其他例如File和URL类型的数组排序，因为它们都实现了Comparable接口。同一段代码能够适应所有这些类型的数据是非常方便的，但一般的应用程序中需要排序的数据类型都是应用程序自己定义的。相应，在自定义的数据类型中实现一个compareTo()方法也是很常见的，这样就实现了Comparable接口，也就使得这种数据类型可以被排序了(也可以用其构造优先队列)。
5.8.1.1 交易事务
排序算法的一种典型应用就是商业数据处理。例如，设想一家互联网商业公司为每笔交易记录都保存了所有的相关信息，包括客户名、日期、金额等。如今，一家成功的商业公司需要能够处理数百万的这种交易数据。一种合适的方法是将交易记录按金额大小排序，我们在类的定义中实现一个恰当的compareTo()方法就可以做到这一一点。 这样我们在处理Transaction 类型的数组a[]时就可以先将其排序，比如这样Quick. sort(a)。我们的排序算法对Transaction类型无所知，但Java的Comparable接口使我们可以为该类型定义大小关系，这样我们的任意排序算法都能够用于Transaction对象了。或者我们也可以令Transaction对象按照日期排序(如下面的代码所示)，将compareTo()方法实现为比较Date字段。因为Date对象本身也实现了Comparable接口,我们可以直接调用它的compareTo()方法而不用自己实现了。将这种类型按照用户名排序也是合理的。使算法的用例能够灵活地用不同的字段排序则是我们在稍后将要面对的另一项有趣的挑战。
将交易记录按照日期排序的compareTo()方法
public int compareTo(Transaction that){
return this.when. compareTo(that .when);
}
5.8.1.2 指针排序
我们使用的方法在经典教材中被称为指针排序,因为我们只处理元素的引用而不移动数据本身。在其他编程语言例如C和C++之中，程序员需要明确地指出操作的是数据还是指向数据的指针，而在Java中，指针操作是隐式的。除了原始数字类型之外，我们操作的总是数据的引用而非数据本身。指针排序增加了一层间接性, 因为数组保存的是待排序的对象的引用，而非对象本身。我们会简要讨论- -些相关的问题。对于多个引用数组，我们可以将同一组数据的不同部分按照多种方式排序(可能会用到下面提到的多键)。
5.8.1.3 不可变的键
如果在排序后用例还能够修改键值，那么数组就很可能不再是有序的了。类似,优先队列在用例能够修改键值的情况下也不太可能正常工作。在Java中，可以用不可变的数据类型作为键来避免这个问题。大多数你可能用作键的数据类型，例如String, Integer, Double和File都是不可变的。
5.8.1.4 廉价的交换
使用引用的另一个好处是我们不必移动整个元素。对于元素大而键小的数组来说这带来的节约是巨大的，因为比较只需要访向元素的一小部分，而排序过程中大部分元素都不会被访问到。对于几乎任意大小的元素，使用引用使得在一般情况 下交换的成本和比较的成本几乎相同(代价是需要额外的空间存储这些引用)。如果键值很长，那么交换的成本甚至会低于比较的成本。研究将数字排序的算法性能的-种方法就是观察其所需的比较和交换总数，因为这里隐式地假设了比较和交换的成本是相同的。由此得出的结论则适用于Java中的许多应用，因为我们都是在将引用排序。
5.8.1.5 多种排序方法
在很多应用中我们都希望根据情况将一组对象按照不同的方式排序。Java 的Comparator接口允许我们在一个类之中实现多种排序方法。它只有一个compare()方法来比较两个对象。如果一种数据类型实现了这个接口， 我们可以像上面的中的例子那样将另一个实现了Comparator接口的对象传递给sort()方法，sort()再将其传递给less()。Comparator接口允许我们为任意数据类型定义任意多种排序方法。用Comparator接口来代替Comparable接口能够更好地将数据类型的定义和两个该类型的对象应该如何比较的定义区分开来。事实上，比较两个对象的确可以有多种标准，Comparator 接口使得我们能够在其中进行选择。例如，想在忽略大小写的情况下将字符串数组a[]排序，可以使用Java的string类型中定义的CASE. INSENSITVE_ORDER比较器并调用Insertion. sort(a, String. CASE INSENSITIVE ORDER)。你也知道，精确定义的字符串排序规则十分复杂，而各种自然语言又差异很大，所以Java的String类型含有很多比较器。
5.8.1.6 多键数组
一般在应用程序中，一个元素的多种属性都可能被用作排序的键。在交易的例子中，有时可能需要将交易按照客户排序(例如，找出每个客户进行的所有交易);有时又可能需要按照金额排序(例如，需要找出交易金额较高的交易) ;有时还可能用另一个属性来排序。要实现这种灵活性，Comparator 接口正合适。我们可以定义多种比较器，如Transaction类的另一种实现那样。在这样定义之后，要将Transaction对象的数组按照时间排序可以调用:
Insertion. sort(a, new Transaction. When0rder())
或者这样来按照金额排序:
Insertion.sort(a, new Transaction.HowMuchOrder())
sort()方法在每次比较中都会回调Transaction类中用例指定的compare()方法。为了避免每次排序都创建一个新的Comparator对象，我们使用了public final 来定义这些比较器(代码如下，就像Java定义的CASE INSENSITIVE ORDER一样):
使用了Comparator的插入排序
public static void sort(Object[] a, Comparator c){
int N = a.length;
for(int i =0;i < N; N; i+t){
for (int j-1; j> 0& less(C, a[i], a[j-1]; j--){
exch(a,j,j-1);
}
}
privete statc boolean lsSsarator ( Object v，Object w){
return c.compare(v,w) < 0;
}
private static void exch(Object[] a, int i, int j){
Object t = a[i];
a[i] = a[j];
a[j] = t;
}
}
5.8.1.7 使用比较器实现优先队列
比较器的灵活性也可以用在优先队列上。我们可以按照以下步骤来扩展算法2.6的标准实现来支持比较器:
1.导入java.util. Comparator;
2.为MaxPQ添加一个实例变量comparator以及一个构造函数，该构造函数接受一·个比较器作为参数并用它将comparator初始化;
3.在less()中检查comparator属性是否为null (如果不是的话就用它进行比较)。实现代码如下:
使用了Comparator的插入排序
mport java.util. Comparator;
public class Transaction{
private final String who;
private final Date when;
private final double amount;
public static class Whorder implements Comparator<Transaction>{
public int compare(Transaction v, Transaction w){
return v.who.compareTo(w.who);
}
}
public static class WhenOrder implements Comparator<Transaction>{
public int compare(Transaction v, Transaction w){
return v.when.compareTo(w.when);
}
}
public static class HowMuchOrder implements Comparator<Transaction>{
public int compare(Transaction v, Transaction w){
if (v.amount < w.amount) return -1;
if (V. amount > w. amount) return +1;
return 0;
}
}
}
例如，修改后可以使用Transaction的多种字段构造不同的优先队列，分别按照时间、地点、账号排序。如果你在MinPQ中去掉了Key extends Comparable 这句话，甚至可以支持尚未定义过比较方法的键。
5.8.1.8 稳定性
如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。这个性质在许多情况下很重要。例如，考虑一个需要处理大量含有地理位置和时间戳的事件的互联网商业应用程序。首先，我们在事件发生时将它们挨个存储在一个数组中 ，这样在数组中它们已经是按照时间顺序排好了的。现在假设在进步处理前将按照地理位置切分。一种简单的方法是将数组按照位置排序。如果排序算法不是稳定的，排序后的每个城市的交易可能不会再是按照时间顺序排列的了。很多情况下，不熟悉排序稳定性的程序员在第一次遇见这种情形时会惊讶于不稳定的排序算法似乎把数据弄得一团糟。在本章中，我们学习过的一部分算法是稳定的(插人排序和归并排序)，但很多不是(选择排序、希尔排序、快速排序和堆排序)。有很多办法能够将任意排序算法变成稳定的，但一般只有在稳定性是必要的情况下稳定的排序算法才有优势。人们很容易觉得算法具有稳定性是理所当然的，但事实上没有任何实际应用中常见的方法不是用了大量额外的时间和空间才做到了这一点。
