排序 #
初级排序算法 #
选择排序 #
命题A。对于长度为N 的数组，选择排序需要大约 N^2/2 次比较和N 次交换。
代码
public class Selection { public static void sort(Comparable[] a) { // 将a[]按升序排列 int N = a.length; // 数组长度 for (int i = 0; i < N; i++) { // 将a[i]和a[i+1..N]中最小的元素交换 int min = i; // 最小元素的索引 for (int j = i+1; j < N; j++) if (less(a[j], a[min])) min = j; exch(a, i, min); } } // less()、exch()、isSorted()和main()方法见“排序算法类模板” }特点
- 运行时间与输入无关，即输入数据的初始状态（比如是否已排序好等等）不影响排序时间
- 数据移动是最少的（只使用了N次交换，交换次数和数组的大小是线性关系
插入排序 #
命题B。对于随机排列的长度为N 且主键不重复的数组，平均情况下插入排序需要～ N2/4 次比较以及～ N2/4 次交换。最坏情况下需要～ N2/2 次比较和～ N2/2 次交换，最好情况下需要N-1次比较和0 次交换。
代码
public static void sort(Comparable[] a) { int N = a.length; //将下表为 n-1的数，依次和n-2,n-3一直到0比较， //所以第二层for只走到1，因为0前面没有值 //如果比前面的值小，就进行交换 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); } } }当倒置的数量很小时，插入排序比本章中的其他任何算法都快
命题C。插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。
性质D。对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数
希尔排序 #
希尔排序的思想是使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组，一个h有序数组就是h个互相独立的有序数组编制在一起组成的数组
算法2.3 的实现使用了序列1/2（3k-1），从N/3 开始递减至1。我们把这个序列称为递增序列
详述
实现希尔排序的一种方法是对于每个h，用插入排序将h 个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在h- 子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要在插入排序的代码中将移动元素的距离由1 改为h 即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。
代码
public class Shell { public static void sort(Comparable[] a) { // 将a[]按升序排列 int N = a.length; int h = 1; while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... while (h >= 1) { // 将数组变为h有序 for (int i = h; i < N; i++) { // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) exch(a, j, j-h); } h = h/3; } } // less()、exch()、isSorted()和main()方法见“排序算法类模板” }通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一
归并排序 #
归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比，主要缺点是他所需的额外空间和N成正比
- 归并排序示意图
自顶向下的归并排序 #
原地归并的抽象方法
/** * 这里有一个前提，就是a[i..mid]是有序的， * a[mid..hi]是有序的 * * @param a * @param lo * @param mid * @param 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]; } //最坏情况下这里时需要比较hi-lo+1次的，也就是数组长度 for (int k = lo; k <= hi; k++) { if (i > mid) { //说明i(左边）比较完了，直接拿右边的值放进去 a[k] = aux[j++]; } else if (j > hi) { //说明j(右边)比较完了，直接拿左边的值放进去 a[k] = aux[i++]; } else if (less(aux[j], aux[i])) { //左右都还有值的情况下，取出最小的值放进去 a[k] = aux[j++]; } else { a[k] = aux[i++]; } } }递归进行归并排序
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); }辅助数组的一次性初始化
private static Comparable[] aux; public static void sort(Comparable[] a) { aux = new Comparable[a.length];//辅助数组，一次性分配空间 sort(a, 0, a.length - 1); }自顶向下的归并排序的调用轨迹
N=16时归并排序中子数组的依赖树
每个结点都表示一个sort() 方法通过merge() 方法归并而成的子数组。这棵树正好有n 层。对于0 到n-1 之间的任意k，自顶向下的第k 层有2k 个子数组，每个数组的长度为 $2{(n-k)}$，归并最多需要$2^{(n-k)}$次比较。因此每层的比较次数为$ 2k * 2 ^ {( n - 1 )} = 2 ^ n $ ，n层总共为 $n*2n = lg N * (2 ^ { lg N}) = lg N * N$
命题F。对于长度为N 的任意数组，自顶向下的归并排序需要(1/2)N lgN 至N lgN 次比较。
注：因为归并所需要的比较次数最少为N/2
命题G。对于长度为N 的任意数组，自顶向下的归并排序最多需要访问数组6NlgN 次。 证明。每次归并最多需要访问数组6N 次（2N 次用来复制，2N 次用来将排好序的元素移动回去，另外最多比较2N 次），根据命题F 即可得到这个命题的结果。
自底向上的归并排序 #
递归实现的归并排序时算法设计中分治思想 的典型应用
自底向上的归并排序的可视轨迹
源代码
private static Comparable[] aux; private static void sort(Comparable[] a) { int N = a.length; aux = new Comparable[N]; //每次合并的子数组长度翻倍 for (int sz = 1; sz < N; sz = sz + sz) { //lo:子数组索引 //边界问题， 假设是N为2^n，则倒数第二个数组的元素的下标，一定在倒数第一个元素下标(n-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)); } } }子数组的大小sz的初始值为1，每次加倍
最后一个子数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz（否则比sz小)
命题H。对于长度为N 的任意数组，自底向上的归并排序需要1/2NlgN 至NlgN 次比较，最多访问数组6NlgN 次。
自底向上的归并排序比较适合用链表组织的数据。想象一下将链表先按大小为1 的子链表进行排序，然后是大小为2 的子链表，然后是大小为4 的子链表等。这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建任何新的链表结点）
归并排序告诉我们，当能够用其中一种方法解决一个问题时，都应该试试另一种，可以像Merge.sort()那样化整为零（然后递归地解决）问题，或者像MergeBU.sort()那样循序渐进的解决问题
命题I。没有任何基于比较的算法能够保证使用少于lg（N!）～ NlgN 次比较将长度为N 的数组排序
命题J。归并排序是一种渐进最优的基于比较排序的算法。
快速排序 #
快速排序是应用最广泛的排序算法
基本算法 #
是一种分治的排序算法，将一个数组分成两个子数组，将两部分独立的排序
归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将两个数组排序；快速排序将数组排序的方式是当两个子数组都有序时整个数组也都有序了
归并排序：递归调用发生在处理数组之前；快速排序：递归调用发生在处理数组之后
归并排序中数组被分为两半；快速排序中切分取决于数组内容
快速排序示意图
递归代码
public 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]排序 }快速排序递归的将子数组a[lo..hi]排序，先用partition()方法将a[j]放到一个合适的位置，然后再用递归调用将其他位置的元素排序
切分后使得数组满足三个条件
- 对于某个j，a[j]已经排定
- a[lo]到a[j-1]的所有元素都不大于a[j]
- a[j+1]的所有元素都不小于a[j]
归纳法证明数组有序：
如果左子数组和右子数组都是有序的，那么由左子数组（有序且没有任何元素大于切分元素）、切分元素和右子数组（有序且没有任何元素小于切分元素）组成的结果数组也一定是有序的
一般策略是先随意地取a[lo] 作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。如此继续，我们就可以保证左指针i 的左侧元素都不大于切分元素，右指针j 的右侧元素都不小于切分元素。当两个指针相遇时，我们只需要将切分元素a[lo] 和左子数组最右侧的元素（a[j]）交换然后返回j 即可
代码如下
private static int partition(Comparable[] a, int lo, int hi) { int i = lo, j = hi + 1; //左右扫描指针 Comparable v = a[lo]; //切分元素 while (true) { //从左往右扫描，如果找到了大于等于v值的数，就退出循环 while (less(a[++i], v)) { if (i == hi) break; } //从右往左扫描，如果找到了小于等于v值得数，就退出循环 while (less(a[--j], v)) { if (j == lo) break; } if (i >= j) break;//如果i，j相遇则退出循环 //将左边大于等于v值的数与右边小于等于v值的数交换 exch(a, i, j); } //上面的遍历结束后，a[lo+1...j]和a[i..hi]都已经分别有序 //且a[j]<=a[i]<=a[lo]，所以应该交换a[lo]和a[j](而不是a[i)，因为 //a[i]有可能大于a[lo] exch(a, lo, j); //返回a[lo]被交换的位置 return j; }切分轨迹
性能特点 #
将长度为N的无重复数组排序，快速排序平均需要~2N lnN 次比较（以及1/6的交换）
算法改进 #
三向切分