算法第4版 第2章排序

综述：5个小节，四种排序+应用，初级排序、归并排序、快速排序、优先队列

===2.1.初级排序===

排序算法模板，less(), exch(), 排序代码在sort()方法中；

选择排序：如升序排列，1.找到数组中最小的元素；2.与数组中的第一个元素交换下位置；3.再在剩下的元素找最小值，与第二个元素交换下位置；重复，直到所有元素都完成排序。

交换的总次数是n，算法的时间效率取决于比较次数(N2/2);

选择排序时间复杂度（O(n2)）,两个特点：运行时间与输入无关；数据移动是最少的;

选择排序的实现:

private static boolean less(Comparable v, Comparable w){

return v.compareTo(w)<0;

}

public static void exch(Comparable[]a, int i, int j){

Comparable t = a[i]; a[i]=a[j];a[j]=t;

}

public class Selection{

public static void sort(Comparable[]){

int N = a.length;

for(int i = 0; i<N;i++){

int min =i;

for(int j =i+1;j<N;j++){

if(less a[j], a[min]) min =j;

exch(a, i, min);

}

}

}

冒泡排序：一次比较两个元素，如果位置不对就交换，一次遍历要交换多次

插入排序：第i个元素与第i之前的元素对比，插入到合适的位置。左侧部门一直为有序数组

对于随机排列的长度未N且主键不重复的数组，平均情况下插入排序需要N2/4比较，N2/4次交换。最坏情况下需亚奥N2/2, N2/2次交换。插入排序对有序数组的排序，运行时间是线性的。

代码实现：

publIc class Insertion{

public static void sort(Comparable[] a){

int N = a.length;

for(int i = 1; i<N; i++){

for(int j =1; j>0&&less(a[j], a[j-1]); j--)

exch(a, j, j-1);

}

}

}

部分有序数组：数组中的每个元素距离它的最终位置都不远；一个有序的大数组接一个小数组；数组中只有几个元素的位置不正确。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组（见图2.1.2）。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。

代码实现：

public class Shell{

public static void sort(Comparable[] a){

int N = a.length;

int h =1;

while(h<N/3) h = 3*h+1;

while(h>=1){

for(int i =h; i<N; i++){

for(int j=i, j>=h&&less(a[j],a[j-h]); j -=h)

exch(a, j, j-h);

}

h = h/3;

}

}

}

===2.2 归并排序===

归并，将两个有序数组归并成一个更大的有序数组。

归并排序，能够保证任意长度为N的数组排序所需时间和NlogN成正比，缺点是所需的额外空间与N成正比。

实现归并直接的方法，将两个不同的有序数组归并到第三个数组中，创建一个适当大小的数组，然后将两个输入数组的元素一个个从小到大放入这个数组中。

归并一个大数组时，需进行多次归并，每次归并都要创建一个新数组存储排序结果。通过原地归并，先将前半部分排序，再将后半部分排序，在数组中移动元素而不需要使用额外的空间。

merge(a, lo, mid, hi)它会将子数组a[lo...mid]和a[mid+1..hi]归并成一个有序数组，并将结果存放在a[lo..hi]，

原地归并的抽象方法：

public static void merge(Comparable[] a, int lo, int mid, int hi){

int i = lo, j+mid+1;

for(int k =lo; k <= hi; k++) aux[k] = a[k];

for(int k =lo; k<=hi; k++)

if(i>mid) a[k]=aux[j++];

else if(j >hi) a[k]=aux[i++];

else if(less(aux[j], aux[i])) a[k] =aux[j++];

else a[k]=aux[i++];

}

该方法先将所有元素复制到aux[], 然后再归并回a[],方法再归并时进行了4个条件判断，左半边用尽（取右半边元素），右半边用尽（取左半边元素），右半边的当前元素小于左半边的当前元素（取右半边的元素），以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）

自顶向下的归并排序

public class Merge{

private static Comparable[] aux;

public static void sor(Comparable[] a){

aux = new Comparable[a.length];

sort(a, a.length-1);

}

private static void sort(Comparable[] a, int lo, int hi){

if(hi<=lo) return;

int mid = lo+(hi-lo)/2;

sort(a, lo, mid);

sort(a, mid+1, hi);

merge(a, lo, mid, hi);

}

}

自底向上的归并排序

public class MergeBu{

private static Comparable[] aux;

public static void sort(Comparable[] a){

int N =a.length;

aux = new Comparable[N];

for(int sz =1; sz<N; sz =sz+sz){

for(int lo=0; lo<N-sz; lo+=sz+sz)

merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

}

}

}

===2.3快速排序===

快速排序时间复杂度(O(nlogn));

特点：原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。

快速排序：分治的排序算法，将一个数组分成两个子数组，独立的排序。与归并排序互补，

并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。

在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容

public class Quick

{ public static void sort(Comparable[] a) {

StdRandom.shuffle(a)

; // 消除对输入的依赖 sort(a, 0, a.length -1); }

private static void sort(Comparable[] a, int lo, int hi)

{ if (hi ＜= lo) return; int j = partition(a, lo, hi); // 切分（请见“快速排序的切分”）

sort(a, lo, j-1); // 将左半部分a[lo .. j-1]排序

sort(a, j+1, hi); // 将右半部分a[j+1 .. hi]排序

} }

该方法的关键在于切分，这个过程使得数组满足下面三个条件：?对于某个j, a[j]已经排定；? a[lo]到a[j-1]中的所有元素都不大于a[j]；? a[j+1]到a[hi]中的所有元素都不小于a[j]。通过递归地调用切分来排序的。

因为切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序：如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素）、切分元素和右子数组（有序且没有任何元素小于切分元素）组成的结果数组也一定是有序的。

需要实现切分方法。一般策略是先随意地取a[lo]作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。

当两个指针相遇时，我们只需要将切分元素a[lo]和左子数组最右侧的元素（a[j]）交换然后返回j即可

快速排序的最好情况是每次都正好能将数组对半分。在这种情况下快速排序所用的比较次数正好满足分治递归的CN=2CN/2+N公式。2CN/2表示将两个子数组排序的成本，N表示用切分元素和所有数组元素进行比较的成本

几个细节问题：原地切分、别越界、保持随机性、终止循环、处理切分元素值有重复的情况、终止递归

算法改进：

切换到插入排序（对于小数组，快速排序比插入排序慢；因为递归，快速排序的sort()方法在小数组中也会调用自己）；

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。人们发现将取样大小设为3并用大小居中的元素切分的效果最好；

熵最优的排序，含有大量重复元素的数组，一个元素全部重复的子数组就不需要继续排序了，但我们的算法还会继续将它切分为更小的数组，一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂

==2.4优先队列===

许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素

例如，你可能有一台能够同时运行多个应用程序的电脑（或者手机）。这是通过为每个应用程序的事件分配一个优先级，并总是处理下一个优先级最高的事件来实现的。例如，绝大多数手机分配给来电的优先级都会比游戏程序的高。

在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列（删除最老的元素）以及栈（删除最新的元素）类似。

基于二叉堆数据结构的一种优先队列的经典实现方法，用数组保存元素并按照一定条件排序，以实现高效地（对数级别的）删除最大元素和插入元素操作。

优先队列的一些重要的应用场景包括模拟系统，其中事件的键即为发生的时间，而系统需要按照时间顺序处理所有事件；任务调度，其中键值对应的优先级决定了应该首先执行哪些任务；

泛型优先队列的API，优先队列是一种抽象数据类型（请见1.2节），它表示了一组值和对这些值的操作。优先队列最重要的操作就是删除最大元素和插入元素，删除最大元素的方法名为delMax()，插入元素的方法名为insert()

优先队列的调用示例：考虑以下问题：输入N个字符串，每个字符串都对应着一个整数，你的任务就是从中找出最大的（或是最小的）M个整数（及其关联的字符串）。要我们能够高效地实现insert()和delMin()，下面的优先队列用例中调用了MinPQ的TopM就能使用优先队列解决这个问题。

初级实现：数组实现（无序）、数组实现（有序）、链表表示法

堆的定义：数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素。

当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点（父结点和两个子结点各需要一个）。

由下至上的堆有序化（上浮）、由上至下的堆有序化（下沉）、多叉堆、调整数组大小、元素的不可变性、索引优先队列、索引优先队列用例。

用基于堆的优先队列这样做等同于哪种排序？一种全新的排序方法！下面我们就用堆来实现一种经典而优雅的排序算法——堆排序。

堆排序可以分为两个阶段。在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。

从右至左用sink()函数构造子堆。数组的每个位置都已经是一个子堆的根结点了，sink()对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了，那么在该结点上调用sink()可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆。最后我们在位置1上调用sink()方法，扫描结束。

堆的构造、下沉排序、先下沉后上浮。

堆排序在排序复杂性的研究中有着重要的地位，因为它是我们所知的唯一能够同时最优地利用空间和时间的方法——在最坏的情况下它也能保证使用～2NlgN次比较和恒定的额外空间。

2.5 应用

排序如此有用的一个主要原因是，在一个有序的数组中查找一个元素要比在一个无序的数组中查找简单得多。只要队列是有序的，很多其他任务也更容易完成。

排序算法的一种典型应用就是商业数据处理。

我们在类的定义中实现一个恰当的compareTo()方法就可以做到这一点。这样我们在处理Transaction类型的数组a[]时就可以先将其排序，比如这样Quick.sort(a)。我们的排序算法对Transaction类型一无所知，但Java的Comparable接口使我们可以为该类型定义大小关系，这样我们的任意排序算法都能够用于Transaction对象了。

Java系统库的排序算法，这里我们考虑Java系统库中的主要排序方法java.util. Arrays.sort()。

ava的系统程序员选择对原始数据类型使用（三向切分的）快速排序，对引用类型使用归并排序。这些选择实际上也暗示着用速度和空间（对于原始数据类型）来换取稳定性（对于引用类型）。

排序应用一览：商业计算、信息搜索（有序的信息确保我们可以用经典的二分查找法（见第1章）来进行高效的搜索）、运筹学、事件驱动模拟、数值计算、组合搜索