1.Rules
public class Example{ //how to sort public static void sort(Comparable[] a){ ... } //v compare with w public static boolean less(Comparable v,Comparable w){ return v.compareTo(w)<0; } //exchange public static void exch(Comparable[] a,int i,int j){ Comparable t=a[i]; a[i]=a[j]; a[j]=t; } //print public static void show(Comparable[] a){ for(int i=0;i<a.length;i++){ StdOut.print(a[i]+" "); } StdOut.println(); } //testing this array whether is sorted or not public static boolean isSorted(Compareble[] a){ for(int i=1;i<a.length;i++){ if(less(a[i],a[i-1])){ return false; } } return true; }
2.Selection Sort
首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组第二个元素交换位置。如此往复，直到将整个数组排序。
public static void selection(Comparable[] a) { 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); } } }
选择排序的内循环只是在比较当前元素与目前已知的最小元素（以及将当前索引加1和检查是否代码越界）。交换元素的代码写在内循环之外，每次交换都能排定一个元素，因此交换的总次数是N。所以算法的时间效率取决于比较的次数。
命题A：对于长度为N的数组，选择排序需要大约N*N/2次比较和N次交换。
选择排序的两个鲜明的特点：
1）运行时间和输入无关。
2）数据移动是最少的。
3.Insertion Sort
通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的位置。在计算机实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。
与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。
和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。插入排序对于实际应用中常见的某些类型的非随机数组很有效。
命题B：对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要~N*N/4次比较以及~N*N/4次交换。最坏情况下需要~N*N/2次比较和~N*N/2次交换，最好情况下需要N-1次比较和0次交换。
public static void insertion(Comparable[] a) { int N = a.length; for (int i = 1; i < N; i++) { for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { exch(a, j, j - 1); } } }
对于1到N-1之间的每一个i，将a[i]与a[0]到a[i-1]中比它小的所有元素依次有序地交换。在索引i由左向右变化的过程中，它左侧的元素总是有序的，所以当i到达数组的右端时排序就完成了。
我们要考虑的更一般的情况是部分有序的数组。下面是几种典型的部分有序的数组：
1）数组中每个元素距离它的最终位置都不远。
2）一个有序的大数组接一个小数组。
3）数组中只有几个元素的位置不正确。
插入排序对这样的数组很有效。事实上，当倒置的数量很少时，插入排序很可能比很多算法都要快。
命题C：插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置数量，小于等于倒置的数量加上数组的大小再减一。
要大幅度提高插入排序的速度并不难，只需要在内循环中将较大的元素向右移动而不总是交换两个元素（这样访问数组的次数就能减半）。
public static void sort(Comparable[] a) { int N = a.length; for (int i = 1; i < N; i++) { Comparable temp = a[i]; int j = i; for (; j > 0 && less(temp, a[j - 1]); j--) { a[j] = a[j - 1]; } a[j] = temp; } }
4.Shell Sort
对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序，这就是希尔排序。
实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在h-子数组中将每个元素交换到比它大的元素之前去。只需要在插入排序的代码中将移动元素的距离由1改为h即可。这样，希尔排序的实现就转换为了一个类似于插入排序但使用不同增量的过程。
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。
public static void shell(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; } }
4.Merge Sort
要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后再将结果归并起来。这就是归并排序。
实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中，两个数组中的元素应该都实现了Comparable接口。实现的方法很简单，创建一个适当大小的数组然后将两个输入数组中的元素一个个从小到大放入这个数组中。
但是，当用归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一个新数组来存储排序结果会带来问题。我们更希望有一种能够在原地归并的方法，这样就可以先将前半部分排序，再将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。
尽管如此，将原地归并抽象化依然是有帮助的。与之对应的是我们的方法签名merge(a,lo,mid,hi)，它会将子数组a[lo..mid]和a[mid+1..hi]归并成一个有序的数组并将结果存放在a[lo..hi]中。
public static void merge(Comparable[] a, int low, int mid, int high) { int i = low; int j = mid + 1; for (int k = low; k <= high; k++) { aux[k] = a[k]; } for (int k = low; k <= high; k++) { if (i > mid) { a[k] = aux[j++]; } else if (j > high) { a[k] = aux[i++]; } else if (less(aux[j], aux[i])) { a[k] = aux[j++]; } else { a[k] = aux[i++]; } } }
该方法先将所有元素复制到aux[]中，然后再归并回a[]中。方法在归并时（第二个for循环）进行了4个条件判断：左半边用尽（取右半边的元素），右半边用尽（取左半边的元素），右半边的当前元素小于做半边的当前元素（取右半边的元素）以及右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。
1).自顶向下的归并排序
基于原地归并的抽象实现了另一种递归归并，这也是应用高效算法设计中分治思想的最典型的一个例子。
public class Merge { private static Comparable[] aux; public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, 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); }
要将子数组a[lo..hi]进行排序，先将它分为a[lo..mid]和a[mid+1..hi]两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。
命题F：对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN至NlgN次比较。
归并排序所需的时间和NlgN成正比。但归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。
还可以对归并排序进行进一步改进：
1）对小规模子数组使用插入排序。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%～15%。
2）测试数组是否已经有序。我们可以添加一个判断条件，如果a[mid]小于等于a[mid+1]，我们就认为数组已经是有序的并跳过merge()方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了。
3）不将元素复制到辅助数组。我们可以节省将数组元素复制到用于归并的辅助数组所用的时间（但空间不行）。要做到这一点我们要调用两种排序方法，一种将数据从输入数组排序到辅助数组，一种将数据从辅助数组排序到输入数组。
public class Example { private static int CUTOFF = 15; public static void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { dest[k] = src[j++]; } else if (j > hi) { dest[k] = src[i++]; } else if (less(src[j], src[i])) { dest[k] = src[j++]; } else { dest[k] = src[i++]; } } } public static void sort(Comparable[] a) { Comparable[] aux = a.clone(); sort(aux, a, 0, a.length - 1); } private static void sort(Comparable[] src, Comparable[] dest, int lo, int hi) { if (hi - lo < CUTOFF) { insertionSort(dest, lo, hi); return; } int mid = lo + (hi - lo) / 2; sort(dest, src, lo, mid); sort(dest, src, mid + 1, hi); if (less(src[mid + 1], src[mid])) { merge(src, dest, lo, mid, hi); } }
2).自底向上的归并排序
实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并并得到的子数组，如此这般，直到我们将整个数组归并在一起。
首先，我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八的归并，一直下去。
在每一轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小（但这对merge()方法不是问题），如果不是的话所有的归并中两个数组大小都应该一样，而在下一轮中子数组的大小会翻倍。
public static void DownTopSort(Comparable[] a) { int N = a.length; aux = new Comparable[N]; for (int sz = 1; sz < N; sz = sz + sz) { for (int low = 0; low < N - sz; low += sz + sz) { merge(a, low, low + sz - 1, Math.min(low + sz + sz - 1, N - 1)); } } }
自底向上的归并排序会多次遍历整个数组，根据子数组大小进行两两归并。子数组的大小sz的初始值为1,每次加倍。最后一个子数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz（否则它会比sz小）。
自底向上的归并排序比较适合用链表组织的数据。
5.Quick Sort
快速排序是一种分治的排序算法。它将一个数组分成两个子数组没，将两部分独立地排序。
快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分(partition)的位置取决于数组的内容。
public static void quick(Comparable[] a) { StdRandom.shuffle(a); quick(a, 0, a.length - 1); } private static void quick(Comparable[] a, int low, int high) { if (high <= low) { return; } int j = partition(a, low, high); quick(a, low, j - 1); quick(a, j + 1, high); }
快速排序递归地将子数组a[lo..hi]排序，先用patition()方法将a[j]放到一个合适位置，然后再用递归调用将其他位置的元素排序。
该方法的关键在于切分，这个过程使得数组满足下面三个条件：
1)对于某个j，a[j]已经排定。
2)a[lo]到a[j-1]中的所有元素都不大于a[j]。
3)a[j+1]到a[hi]中的所有元素都不小于a[j]。
我们就是通过递归地调用切分来排序的。
因为切分过程总是能排定一个元素，用归纳法不难证明递归能够正确地将数组排序：如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素），切分元素和右子数组（有序且没有任何元素小于切分元素）组成的结果数组也一定是有序的。
要完成这个实现，需要实现切分方法。一般策略是先随意地取a[lo]作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。如此继续，我们就可以保证左指针i的左侧元素都不大于切分元素，右指针j的右侧元素都不小于切分元素。当两个指针相遇时，我们只需要将切分元素a[lo]和左子数组最右侧的元素(a[j])交换然后返回j即可。
private static int partition(Comparable[] a, int low, int high) { int i = low; int j = high + 1; Comparable v = a[low]; while (true) { while (less(a[++i], v)) { if (i == high) { break; } } while (less(v, a[--j])) { if (j == low) { break; } } if (i >= j) { break; } exch(a, i, j); } exch(a, low, j); return j; }
这段代码按照a[lo]的值v进行切分。当指针i和j相遇时主循环退出。在循环中，a[i]小于v时我们增大i，a[j]大于v时我们减小j，然后交换a[i]和a[j]来保证i左侧的元素都不大于v，j右侧的元素都不小于v。当指针相遇时交换a[lo]和a[j]，切分结束。
这段快速排序的实现代码还有几个细节问题值得一提，因为它们都可能导致实现错误或是影响性能，我们会在下面讨论。
1)原地切分
如果使用一个辅助数组，我们可以很容易实现切分，但将切分后的数组复制回去的开销也许会使我们得不偿失。一个初级Java程序员甚至可能会将空数组创建在递归的切分方法中，这会大大降低排序的速度。
2)别越界
如果切分元素是数组中最小或最大的那个元素，我们就要小心别让扫描指针跑出数组的边界。partition()实现可进行明确的检测来预防这种情况。测试条件（j==lo）是冗余的，因为切分元素就是a[lo]，它不可能比自己小。数组右端也有相同的情况，它们都是可以去掉的。
3)终止循环
有经验的程序员都知道保证循环结束要格外小心，快速排序的切分循环也不例外。正确地检测指针是否越界需要一点技巧，并不像看上去那么容易。一个最常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。
4)处理切分元素有重复的情况
左侧扫描最好是在遇到大于等于切分元素值的元素时停下，右侧扫描则是遇到小于等于切分元素值的元素时停下，尽管这样可能会不必要地将一些等值元素交换，但在某些典型应用中，它能够避免算法的运行时间变为平方级别。
5)终止递归
有经验的程序员还知道保证递归总是能够结束也是需要小心的，快速排序也不例外。例如，实现快速排序时一个常见的错误就是不能保证将切分元素放入正确的位置， 从而导致程序在切分元素正好是子数组的最大或是最小元素时陷入了无限的递归循环之中。
性能特点
快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。这种简洁性也是快速排序的一个优点。例如，归并排序和希尔排序一般都比快速排序慢，其原因就是它们还在内循环中移动数据。
快速排序的另一个速度优势在于它的比较次数很少。排序效率最终还是依赖切分数组的效果，而这依赖于切分元素的值。切分将一个较大的随机数组分成两个随机子数组，而实际上这种分割可能发生在数组的任意位置（对于元素不重复的数组而言）。
快速排序的最好情况是每次都正好能将数组对半分。但是尽管快速排序有很多优点，它的基本实现仍有一个潜在的缺点：在切分不平衡时这个程序可能会极为低效。
算法改进
1)切换到插入排序
和大多数递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：
a.对于小数组，快速排序比插入排序慢。 b.因为递归，快速排序的sort()方法在小数组也会调用自己。
2)三取样切分
改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。我们还可以将取样元素放在数组末尾作为“哨兵”来去掉partition()方法中的数组边界测试。
public class Ex22 { // cutoff to insertion sort, must be >= 1 private static final int INSERTION_SORT_CUTOFF = 8; // cutoff to median-of-3 partitioning private static final int MEDIAN_OF_3_CUTOFF = 40; // This class should not be instantiated. private Ex22() { } /** * Rearranges the array in ascending order, using the natural order. * * @param a * the array to be sorted */ public static void sort(Comparable[] a) { sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { int n = hi - lo + 1; // cutoff to insertion sort if (n <= INSERTION_SORT_CUTOFF) { insertionSort(a, lo, hi); return; } // use median-of-3 as partitioning element else if (n <= MEDIAN_OF_3_CUTOFF) { int m = median3(a, lo, lo + n / 2, hi); exch(a, m, lo); } // use Tukey ninther as partitioning element else { int eps = n / 8; int mid = lo + n / 2; int m1 = median3(a, lo, lo + eps, lo + eps + eps); int m2 = median3(a, mid - eps, mid, mid + eps); int m3 = median3(a, hi - eps - eps, hi - eps, hi); int ninther = median3(a, m1, m2, m3); exch(a, ninther, lo); } // Bentley-McIlroy 3-way partitioning int i = lo, j = hi + 1; int p = lo, q = hi + 1; Comparable v = a[lo]; while (true) { while (less(a[++i], v)) if (i == hi) break; while (less(v, a[--j])) if (j == lo) break; // pointers cross if (i == j && eq(a[i], v)) exch(a, ++p, i); if (i >= j) break; exch(a, i, j); if (eq(a[i], v)) exch(a, ++p, i); if (eq(a[j], v)) exch(a, --q, j); } i = j + 1; for (int k = lo; k <= p; k++) exch(a, k, j--); for (int k = hi; k >= q; k--) exch(a, k, i++); sort(a, lo, j); sort(a, i, hi); } // sort from a[lo] to a[hi] using insertion sort private static void insertionSort(Comparable[] a, int lo, int hi) { for (int i = lo; i <= hi; i++) for (int j = i; j > lo && less(a[j], a[j - 1]); j--) exch(a, j, j - 1); }
6.Priority Queue
你可能有一台能够同时运行多个应用程序的电脑。这是通过为每个应用程序的事件分配一个优先级，并总是处理下一个优先级最高的事件来实现的。在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。
数据结构二叉堆能够很好地实现优先队列的基本操作。
在二叉堆数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能得到一列非递减的元素。
二叉堆的表示法
如果我们使用完全二叉树，表达就会变得特别方便。完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1,它的子结点在位置2和3,而子结点的子结点则分别在位置4,5,6和7,以此类推。
在一个堆中，位置k的结点的父结点的位置为k/2（向下取整），而它的两个子结点的位置分别为2k和2k+1。这样在不使用指针的情况下我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层就令k等于k/2，向下一层则令k等于2k或2k+1。
命题P：一颗大小为N的完全二叉树的高度为lgN(向下取整)。
堆的算法
我们用长度N+1的私有数组pq[]来表示一个大小为N的堆，我们不会使用pq[0]，堆元素放在pq[1]至pq[N]中。堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化。
在有序化的过程中我们会遇到两种情况。当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。
1)由下至上的堆有序化（上浮）
如果堆的有序状态因为某个结点变得比它的父结点而打破，那么我们就需要通过交换它和它的父结点来修复堆。交换后，这个结点比它的两个两个子结点都大（一个是曾经的父结点，另一个比它更小，因为它是曾经父结点的子结点），但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇到了一个更大的父结点。只要记住位置k的结点的父结点的位置是k/2（向下取整）。
private void swim(int k) { while (k > 1 && less(k / 2, k)) { exch(k / 2, k); k = k / 2; } }
swim()方法中的循环可以保证只有位置k上的结点大于它的父结点时堆的有序状态才会被打破。因此只要该结点不再大于它的父结点，堆的有序状态就恢复了。
2)由上至下的堆有序化（下沉）
如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。交换可能会在子结点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部。由位置为k的结点的子结点位于2k和2k+1可以直接得到对应的代码。
private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) { j++; } if (!less(k, j)) { break; } exch(k, j); k = j; } }
根据上浮与下沉可得出堆的插入元素和删除最大元素的算法。
插入元素：我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素：我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。
public void insert(Key v) { pq[++N] = v; swim(N); } public Key delMax() { Key max = pq[1]; exch(1, N--); pq[N + 1] = null; sink(1); return max; }
7.Heap Sort
我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将他们按顺序删去。
堆排序可以分为两个阶段。在堆的构造中，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。为了和我们已经学习过的代码保持一致，我们将使用一个面向最大元素的优先队列并重复删除最大元素。
堆的构造
从右至左用sink()函数构造子堆。数组的每个位置都已经是一个子堆的根结点，sink()对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了，那么在该结点上调用sink()可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆。最后我们在位置1上调用sink()方法，扫描结束。在排序的第一阶段，堆的构造方法和我们的想象有所不同，因为我们的目标是构造一个堆有序的数组并使最大元素位于数组的开头（次大的元素在附近）而非构造函数结束的末尾。
下沉排序
堆排序的主要工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。
public static void heap(Comparable[] a) { int N = a.length; for (int k = N / 2; k >= 1; k--) { sink(a, k, N); } while (N > 1) { exch(a, 1, N--); sink(a, 1, N); } } private static void sink(Comparable[] a, int k, int N) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) { j++; } if (!less(k, j)) { break; } exch(a, k, j); k = j; } }
这段代码用sink()方法将a[1]到a[N]的元素排序（sink()被修改过，以a[]和N作为参数）。for循环构造了堆，然后while循环将最大的元素a[1]和a[N]交换并修复了堆，如此反复直到堆变为空。将exch()和less()的实现中的索引减一即可的到和其他排序算法一致的实现。