chapter 1 基础
1.1 基础编程模型
-
数组名表示的是整个数组——如果我们将一个数组变量赋予另一个变量，那么两个变量将会指向同一个数组。
int[] a = new int[N]; ... a[i] = 1234; ... int[] b = a; ... b[i] = 5678; //a[i]也会变成5678这种情况叫做 起别名 ，有时可能会导致难以察觉的问题。如果你想将数组复制一份，应该声明、创建并初始化一个新的数组，然后将原数组中的元素挨个复制到新的数组。
1.2 数组抽象
-
数据类型 指的是一组值和一组对这些值的操作的集合。
-
Java编程的基础主要是使用class 关键字构造被称为引用类型的数据类型。
-
对象 是能够承载数据类型的值的实体。所有对象都有三大重要特性：状态、标识和行为 。对象的状态即数据类型中的值。对象的标识就是它在内存中的位置。对象的行为就是数据类型的操作。
-
引用是访问对象的一种方式。Java使用术语引用类型以示和原始数据类型（变量和值相关联）的区别。不同的Java实现中引用的实现细节也各不同，但可以认为引用就是内存地址。
-
构造函数没有返回值，因为它总是返回它的数据类型的对象的引用。
-
每当用例调用了new()，系统都会：1️⃣ 为新的对象分配内存空间； 2️⃣ 调用构造函数初始化对象中的值； 3️⃣ 返回该对象的一个引用。
-
静态方法 的主要作用是实现函数；非静态（实例）方法的主要 作用是实现数据类型的操作。静态方法调用的开头是类名（按习惯为大写），而非静态方法调用的开头总是对象名（按习惯为小写）。
-
使用引用类型的赋值语句将会创建该引用的一个副本。赋值语句不会创建新的对象，而只是创建另一个指向某个已经存在的对象的引用。这种情况叫做别名。
-
创建一个对象的数组需要一下两个步骤：
1️⃣ 使用方括号语法调用数组的构造函数创建数组；
2️⃣ 对于每个数组元素调用它的构造函数创建相应的对象。
1.3 背包、栈、队列
-
集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。一种特别的Java机制能够做到这一点，被称为泛型，也叫做 参数化类型。
-
背包是一种不支持从中删除元素的集合数据类型——他的目的是帮助用例收集元素并迭代遍历所有收集到的元素。迭代的顺序不确定且与用例无关。
-
先进先出队列（简称队列）是一种基于先进先出（FIFO）策略的集合类型。
-
下压栈（简称栈）是一种基于后进先出（LIFO）策略的集合类型。
典型用例：用两个栈解决未省略括号的算术表达式求值：
- 将操作数压入操作数栈；
- 将运算符压入运算符栈；
- 忽略左括号；
- 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
-
链表是一种递归的数据结构，它或者为空(null)，或者是指向一个节点(node)的引用。该结点含有一个泛型的元素和一个指向另一条链表的引用。
private class Node{ Item item; Node next; }两个实例变量：Item(参数类型)和Node；Item是一个占位符，表示任意数据类型；
Node first = new Node() #first是指向一个Node对象的引用，使用first.item和first.next访问它的实例变量。 -
访问链表中所有元素： 将循环的索引变量 x 初始化为链表的首结点。然后通过 x.item 访问和 x 相关联的元素，并将 x 设为 x.next 来访问链表中的下一个结点，如此反复直到 x 为null为止（已经到达了链表的尾部）。
for(Node x = first; x != null; x = x.next){ //处理x.item } -
数组和链表常常被称为顺序存储和链式存储。
-
在泛型中，如果将错误类型的对象压入栈中，会发生 编译时报错 。
-
问：为什么将Node声明为嵌套类？为什么使用private?
答：将Node声明为私有的嵌套类之后，我们可以将Node的方法和实例变量的访问范围限制在包含他的类中。私有嵌套类的一个特点是只有包含他的类能够直接访问它的实例变量，因此无需将它的实例变量声明为public或者private。非静态的嵌套类也被称为内部类。（在写链表结点的定义时，注意是否为嵌套类定义）
-
编写一个函数，接受一条链表的首结点作为参数，（破坏性地）将链表反转并返回结果链表的首结点。
迭代方式的解答：记录链表中的三个连续的结点：reverse、first和second。在每轮迭代中，我们从原链表中提取结点first并将它插入逆链表的开头。我们需要一直保持first指向原链表的所有剩余结点的首结点，second指向原链表中所有剩余结点的第二个结点，reverse指向结果链表的首结点。
public Node reverse(Node x){ Node first = x; Node reverse = null; while(first != null){ Node second = first.next; first.next = reverse; reverse = first; first = second; } return reverse }递归解答： 假设链表含有N个结点，我们先递归颠倒最后N-1个结点，然后小心地将原链表中的首结点插入到结果链表的末端。
public Node reverse(Node first){ if (first == null) return null; if (first.next == null) return first; Node second = first.next; Node rest = reverse(second); second.next = first; first.next = null; return rest; }
1.4 算法分析
-
一个程序运行的总时间主要和两点有关：1️⃣ 执行每条语句的耗时；2️⃣ 执行每条语句的频率。前者取决于计算机、Java编译器和操作系统，后者取决于程序本身和输入。
-
执行最频繁的指令决定了程序执行的总时间——我们将这些指令称之为程序的内循环。许多程序的运行时间都只取决于其中的一小部分指令。
-
统计一个文件中所有和为的三整数元组的数量（ThreeSum问题）
// 暴力破解法 public class ThreeSum{ public static int count(int[] a){ int N = a.length; int cnt = 0; for (int i = 0;i < N; i++) for (int j = i+1; j < N; j++) for (int k = j+1; k < N; k++) if (a[i]+a[j]+a[k] == 0) cnt++; return cnt; } public static void main(String[] args){ int[] a = In.readInts(args[0]); StdOut.println(count(a)); } }ThreeSum 的运行时间的增行数量级是 ，这与它是由Java实现或是它运行在哪台电脑上无关。使用的算法决定了增长的数量级。（可以使用数学归纳法证明从 个数中取三个整数的不同组合的总数为
-
对于大多数程序，得到其运行时间的数学模型所需的步骤如下：
1️⃣ 确定输入模型，定义问题的规模；
2️⃣ 识别内循环；
3️⃣ 根据内循环中的操作确定成本模型；
4️⃣ 对于给定的输入，判断这些操作的执行频率。
for (int i = 1; i < N; i++) for (int j = i+1;j < N; j++) for (int k = j+1; k < N; k++) if (a[i] + a[j] + a[k] == 0) cnt++; -
对增长数量级的常见假设的总结
描述 增长的数量级 典型的代码 说明 举例 常数级别 1 a = a + b 普通语句 将两个数相加 对数级别 二分查找 二分策略 二分查找 线性级别 double max = a[0];
for (int i = 1; i < N; i++)
if (a[i] > max) max = a[i];循环 找出最大元素 线性对数级别 归并排序 分治 归并排序 平方级别 for (int i = 1; i < N; i++)
for (int j = i+1;j < N; j++)
if (a[i] + a[j] == 0) cnt++;双层循环 检查所有元素对 立方级别 for (int i = 1; i < N; i++)
for (int j = i+1;j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] + a[k] == 0) cnt++;三层循环 检查所有三元组 指数级别 ch6 穷举查找 检查所有子集 -
平方级别、立方级别和指数级别的算法对于大规模的问题是不可用的。许多重要问题的直观解法是平方级别的，但我们也可以找到它们线性对数级别的算法。
-
2-sum问题的线性对数级别的解法
首先对数组排序（为二分查找做准备）， 然后对于数组中的每个 a[i] ，使用 BinarySearch 的**rank()**方法对 **-a[i]**进行二分查找。归并排序所需时间和 成正比，二分查找所需的时间和 成正比，因此整个算法的运行时间和 成正比。
import java.util.Arrays; public class TwoSumFast{ public static int count(int[] a){ Arrays.sort(a); //归并排序 int N = a.length; int cnt = 0; for (int i = 0; i < N; i++){ if (BinarySearch.rank(-a[i]， a) > i) cnt++; } return cnt; } public static void main(String[] args){ int[] a = In.readInts(args[0]); Stdout.println(count(a)); } } -
3-sum问题的快速算法
对数组排序并进行 次二分查找，每次查找所需的时间都和 成正比。因此总运行时间和 成正比。
import java.util.Arrays; public class ThreeSumFast{ public static int count(int[] a){ Arrays.sort(a); //归并排序 int N = a.length; int cnt = 0; for (int i = 0; i < N; i++){ for (int j = i+1; j < N; j++) if (BinarySearch.rank(-a[i]-a[j]， a) > j) cnt++; } return cnt; } public static void main(String[] args){ int[] a = In.readInts(args[0]); Stdout.println(count(a)); } } -
调用 substring() 方法时，就创建了一个新的 string 对象（40字节），但是它仍重用了相同的 value[] 数组，因此该字符串的子字符串只会使用40字节的内存。
-
程序调用一个方法时，系统会从内存中的一个特定区域为方法分配所需的内存（用于保存局部变量），这个区域叫做 栈 （Java系统的下压栈）。当方法返回时，它所占用的内存也被返回给了系统栈。因此，在递归程序中创建数组或是其他大型对象是很危险的，因为这意味着每一次递归调用都会使用大量的内存。
-
当通过 new 创建对象时，系统会从 堆内存 的另一块特定区域为该对象分配所需的内存。
1.5 union-find算法
- union-find算法也就是经典的并查集算法，用于解决动态连通性问题.通过对这个算法的一步步更新可以体会到算法优化的思想和好处.
- 基本思想:对于给定的两个触点，判断它们所在的连通分量是否相同，将查找连通分量称为find.如果未连通，则将这两个触点以及分别与它们连通的触点连通，将连通称为union.
- 基础实现:使用一个id数组，保证在同一连通分量中的所有触点在id数组中的值是全部相同的.
- find:返回触点在id数组中对应的值.
- union:分别对p和q进行find操作，如果对应值相等不做操作，不相等则遍历id数组，将所有与p的对应值相等的id值改为q的id值.
- quick-union:改变id数组的定义，每个触点所对应的id元素都是同一个分量中另一个触点的名称，这种联系称为链接.由一个触点的链接一直跟随下去一定会到达根触点，即链接指向子集的触点.当且仅当两个触点的根触点相同时它们存在于同一个连通分量中.
- find:返回一个触点链接的根触点.
- union:分别对p和q进行find操作，如果对应值相等不做操作，不相等则将p的根触点链接到q的根触点上.
- 加权quick-union:为了防止树极度不均衡，记录每一棵树的大小并总是将较小的树连接到较大的树上.在程序中引入size数组记录各个触点的根节点所对应的分量的大小.
- find:返回一个触点链接的根触点.
- union:分别对p和q进行find操作，如果对应值相等不做操作，不相等则判断对应值的根节点分量的大小，将小树的根触点链接到大树的根触点上.
- 路径压缩:为find函数添加一个循环，将在路径上遇到的所有节点都直接链接到根节点.
- 关于并查集，可以参考这篇文章.
chapter 2 排序
2.1 初级排序算法
-
排序算法类的模板
less() 方法对元素进行比较，exch() 方法将元素交换位置。
public class Example{ public static void sort(Comparable[] a){ /* 排序算法 */ } private static boolean less(Comparable v， Comparable w) { return (v.compareTo(w) < 0); } private static void exch(Comparable[] a， int i， int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } private static void show(Comparable[] a){ for (int i = 0; i < a.length; i++) StdOut.println(a[i] + " "); StdOut.println(); } public static boolean isSorted(Comparable[] a){ // 测试数组元素是否有序 for (int i = 1; i < a.length; i++) if (less(a[i]， a[i-1])) return false; return true; } public static void main(String[] args){ String[] a = In.readStrings(); sort(a); isSorted(a); show(a); } } -
排序算法可以分为两类：1️⃣ 除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法；2️⃣ 需要额外内存空间来存储另一份数组副本的其他排序算法。
-
选择排序： 首先找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么就和他自己交换）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此往复，直到将整个数组排序。
public Selection() { public static void sort(Comparable[] 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); } } }对于长度为N的数组，选择排序需要大约 次比较和 次交换。
-
插入排序： 将每一张元素插入到其他已经有序的元素中的适当位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。
public class Insertion { public static void sort(Comparable[] a) { int n = a.length; for (int i = 1; i < n; i++) { //左边已经有序，通过比较将元素找个位置插入 /*例如i=5时，a[0]到a[4]是有序的，比较a[5]和a[4]，如果a[5]比a[4]大，循环终止；如果a[5]比a[4]小，进入for循环，交换a[5]和a[4]；继续，j--，即比较a[4]和a[3]，以此类推；最后将原始的a[5]插入到合适位置；等效于比a[5]大的元素都会向右移动一位*/ for (int j = i; j > 0 && less(a[j]， a[j-1]); j--) { exch(a， j， j-1); } assert isSorted(a， 0， i); } assert isSorted(a); } }对于随机排列的长度为 且主键不重复的数组，平均情况下插入排序需要 次比较以及次交换。最坏情况下需要次比较和次交换，最好情况下需要次比较和次交换。
-
倒置指的是数组中的两个顺序颠倒的元素。比如 中有11对倒置：以及 。如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的。
几种典型的部分有序的数组：1️⃣ 数组中每个元素距离它们的最终位置都不远；2️⃣ 一个有序的大数组借一个小数组；3️⃣ 数组中只有几个元素的位置不正确。
-
插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。
-
要大幅提高插入排序的速度，只需要在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）。
-
希尔排序 的思想是使数组中间隔为 的元素都是有序的。这样的数组被称为h有序数组。在进行排序时，如果很大，就能将元素移动到很远的地方，为实现更小的有序创造方便。用这种方式，对于任意以1结尾的序列，就能够将数组排序，这就是希尔排序。
public class Shell { /** * Rearranges the array in ascending order， using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { int n = a.length; int h = 1; /* 3x+1 increment sequence: 1， 4， 13， 40， 121， 364， 1093， ... */ while (h < n/3) h = 3*h + 1; while (h >= 1) { // h-sort the array 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); } } assert isHsorted(a， h); h /= 3; } assert isSorted(a); } }需要解决一个排序问题而有没有系统排序函数可用时，可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。对于中等大小的数组，它的运行时间是可以接受的，而且代码量小又不需要额外的内存空间。而更加复杂的代码对于很大的 ，可能只会比希尔排序快两倍（可能还达不到）。
2.2 归并排序
-
**归并：**将两个有序的数组归并成一个更大的有序数组。
-
归并排序：要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序可以保证将任意长度为 的数组排序所需时间和 成正比，重要缺点是它所需的额外内存空间和成正比。
-
原地归并的抽象方法
private static void merge(Comparable[] a， Comparable[] aux， int lo， int mid， int hi) { // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays assert isSorted(a， lo， mid); assert isSorted(a， mid+1， hi); // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo， j = mid+1; 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++]; } -
自顶向下的归并排序：分治思想的最典型例子。如果它能够将两个子数组排序，他就能够通过归并两个子数组来将整个数组排序。
public class Merge{ private static Comparable[] aux; // 归并所需的辅助数组 public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a， aux， 0， a.length-1); assert isSorted(a); } private static void sort(Comparable[] a， Comparable[] aux， int lo， int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a， aux， lo， mid); //将左半边排序 sort(a， aux， mid + 1， hi); //将右半边排序 merge(a， aux， lo， mid， hi); //归并结果（“原地归并的抽象方法”） } }对于长度为的任意数组，自顶向下的归并排序需要 至 次比较，最多需要访问数组 次。
-
自底向上的归并排序：首先我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八的归并，一直下去。在每一轮归并中，最后一次归并的第二个子数组可能比第一子数组要小（但这对merge() 方法不是问题）
public class MergeBU { public static void sort(Comparable[] a) { int n = a.length; Comparable[] aux = new Comparable[n]; for (int len = 1; len < n; len *= 2) { for (int lo = 0; lo < n-len; lo += len+len) { int mid = lo+len-1; int hi = Math.min(lo+len+len-1， n-1); merge(a， aux， lo， mid， hi); } } assert isSorted(a); } }对于长度为的任意数组，自顶向下的归并排序需要 至 次比较，最多需要访问数组 次。
当数组长度为2的幂次时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。
-
自底向上的归并排序比较适合用链表组织的数据。将链表先按大小为1的子链表进行排序，然后时大小为2的子链表，然后是大小为4的子链表等。这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建任何新的链表结点）。
-
问：当数组中存在重复的元素时归并排序的表现如何？
答：如果所有的元素都相同，那么归并排序的运行时间将是线性的（需要一个额外的测试避免归并已经有序的数组）。但如果有多个不同的重复值，这样做的性能收益就不是很明显了。例如，假设输入数组的个技术位上的元素都是同一个值，另外个偶数位上的元素都是另一个值，此时算法的运行时间就是线性对数的（这样的数组和所有元素都不重复的数组满足了相同的循环条件），而非线性的。
2.3 快速排序
-
快速排序:时间复杂度为O(NlogN)。将一个数组随机打乱(防止出现最坏情况)，然后通过切分变为两个子数组，将两部分独立地排序，使得切分点左边的所有元素都不大于它，右边的所有元素都不小于它。递归地进行这一过程。
public class Quick { /** * Rearranges the array in ascending order， using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { StdRandom.shuffle(a); sort(a， 0， a.length - 1); assert isSorted(a); } // quicksort the subarray from a[lo] to a[hi] 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); sort(a， j+1， hi); assert isSorted(a， lo， hi); } } -
切分:一般策略是随意取a[low]作为切分元素，然后从数组的左端向右扫描，找到一个大于等于它的元素，再从数组的右端向左扫描，找到一个小于等于它的元素，交换它们的位置。如此继续，直到两个指针相遇时，将切分元素**a[low]和左子数组最右侧的元素a[j]**交换然后返回 j。
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi] private static int partition(Comparable[] a， int lo， int hi) { int i = lo， j = hi + 1; Comparable v = a[lo]; while (true) { // find item on lo to swap while (less(a[++i]， v)) if (i == hi) break; // find item on hi to swap while (less(v， a[--j])) if (j == lo) break; // check if pointers cross if (i >= j) break; exch(a， i， j); } // put partitioning item v at a[j] exch(a， lo， j); // now， a[lo .. j-1] <= a[j] <= a[j+1 .. hi] return j; } -
改进:
-
当子数组较小时(比如长度小于15)使用插入排序
if (hi <= lo + M) {Insertion.sort(a， lo， hi); return;} -
取子数组的一小部分元素(比如3个)的中位数来切分数组，还可以将切分元素放在数组末尾作为哨兵来去掉数组边界测试.
-
如果数组含有大量重复元素，可以采用三向切分的办法，将数组分为小于切分元素，等于切分元素和大于切分元素三部分，它将排序时间降到了线性级别.
public class Quick3way { // quicksort the subarray a[lo .. hi] using 3-way partitioning private static void sort(Comparable[] a， int lo， int hi) { if (hi <= lo) return; int lt = lo， gt = hi; Comparable v = a[lo]; int i = lo + 1; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) exch(a， lt++， i++); else if (cmp > 0) exch(a， i， gt--); else i++; } // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. sort(a， lo， lt-1); sort(a， gt+1， hi); assert isSorted(a， lo， hi); } }
2.4 优先队列
-
优先队列：一种支持删除最大元素和插入元素的数据结构。
-
从N个输入中找到最大的M个元素所需成本呢
增长的数量级 时间 空间 排序算法的用例 调用初级实现的优先队列 调用基于堆实现的优先队列 -
优先队列的各种实现在最坏情况下运行时间的增长数量级
数据结构 插入元素 删除最大元素 有序数组 无序数组 堆 理想情况 -
当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。根结点时堆有序的二叉树的最大结点。
-
二叉堆 是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（为了方便，不使用数组中的第一个位置）。
-
在一个堆中，位置 的结点的父结点的位置为 ，而它的两个子结点的位置则分别为 和 。这样就可以通过计算数组的索引在树中上下移动：从 a[k] 向上一层就令 等于 ，向下一层则令 等于 或 。
-
一颗大小为N的完全二叉树的高度为 。
-
堆的操作会进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称为堆的有序化。
-
由下至上的堆有序化(上浮) ：如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，就需要交换它和它的父结点。位置k的结点的父结点的位置是。重复这个过程直到它不再大于它的父结点为止。
private void swim(int k){ while (k > 1 && less(k/2， k)){ exch(k/2， k); k = 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; } } -
插入元素:将新元素加到末尾，增加堆的大小并让新元素上浮到合适的位置.
-
删除最大元素:从堆顶删去最大的元素，并将最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置。
-
对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过次比较。删除最大元素的操作需要不超过次比较。
-
使用基于堆的优先队列，将所有元素插入一个查找最小元素的优先队列，然后在重复调用删除最小元素的操作来将它们按照顺序删去，即为堆排序。
-
堆排序: 1️⃣ 构造:从数组的中间元素开始，从右到左地对每个元素用下沉方法构造子堆。2️⃣ 排序:将最大的元素a[1]和末尾元素a[N]交换，将堆的大小-1，并对交换到堆顶的末尾元素使用下沉来修复堆，直到堆变空，此时数组中的元素已经有序。
public static void sort(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); } } -
用下沉操作由 个元素构造堆只需要少于 次比较和少于 次交换。而用上浮操作，从左到右遍历数组的时间复杂度是。
-
因为大多数在下沉排序期间重新插入堆的元素会被直接加入到堆底，所以可以使用先下沉后上浮的方法优化，即直接提升较大的子结点直至到达堆底，然后再使元素上浮到正确的位置。
2.5 应用
-
插入排序和归并排序是稳定的，即不会改变重复元素的相对位置。选择排序、希尔排序、快速排序和堆排序则不是稳定的.
-
快速排序是最快的通用排序算法。
-
各种排序算法性能特点
算法 稳定性 是否原地排序 时间复杂度 空间复杂度 备注 选择排序 不稳定 是 $ N^2 $ 插入排序 稳定 是 介于和 取决于输入元素的排列情况 希尔排序 不稳定 是 $NlogN? $ 1 快速排序 不稳定 是 运行效率由概率提供保证 三向快速排序 不稳定 是 介于和 运行效率由概率提供保证，同时取决于输入元素的分布情况。 归并排序 稳定 否 堆排序 不稳定 是 -
归约:为解决某个问题而发明的算法正好可以用来解决另一种问题
- 找出重复元素:首先将数组排序，然后遍历有序的数组，记录连续出现的重复元素即可.
- 排名:求两组数列的Kendall tau距离，即在两组排列中相对顺序不同的数字组数.某个排列和标准排列的Kendall tau距离就是其中逆序数对的数量.可以由其中一个排列确定一个标准索引，然后以这个标准索引为标准对两组数列进行归并排序，移动的次数即为Kendall tau距离.
- 查找中位数:使用快速排序的分割算法，当切分点j小于N/2时只用切分右数组，切分点j大于2/N时只用切分左数组，切分点j=N/2时a[j]即为中位数.如果是海量数据，则可以将数据用二进制表示，根据最大位是0或1划分为两个文件，然后不断对包含中位数的那个文件做此操作，直到可以将剩余的数全部读进内存时再使用快速排序.
chapter 3 查找
3.1 符号表
-
符号表 是一种存储键值对的数据结构，有时也被称为字典 或索引。支持两种操作：插入(put)，即将一组新的键值对存入表中；查找(get)，即根据给定的键得到相应的值。
-
符号表的实现遵循的规则：1️⃣ 每个键只对应着一个值（表中不允许存在重复的键）。2️⃣ 当用例代码向表中存入的键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值。
-
在符号表中，删除的实现有两种方式：1️⃣ 延时删除，就是将键对应的值置为空(null)，然后在某个时候删去所有值为空的键；2️⃣ 即时删除，就是立刻从表中删除指定的键。
-
对于符号表的简单实现（无序），用例的输出中键的顺序是不确定的；对于有序符号表，用例应该就键按顺序打印出来，这是一种索引用例。
-
符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对。在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的值，这叫顺序查找。
public class SequentialSearchST<Key， Value>{ private Node first; //链表首结点 private class Node{ Key key; Value val; Node next; public Node(Key key， Value val， Node next){ this.key = key; this.val = val; this.next = next; } } public Value get(Key key){ for (Node x = first; x != null; x = x.next) if (key.equals(x.key)) return x.val; return null; } public void put(Key key， Value val){ for (Node x = first; x != null; x = x.next) if (key.equals(x.key)){ x.val = val; return; //命中，更新 } first = new Node(key， val， first); // 未命中，新建结点 } }在含有对键值的基于（无序）链表的符号表中，未命中的查找和插入操作都需要次比较。命中的查找在最坏情况下需要次比较，特别地，向一个空表中插入个不同的键需要次比较。
-
有序符号表使用的数据结构是一对平行的数组，一个存储键一个存储值。核心是**rank()**方法，**rank()**方法能够精确地告诉我们到哪里去更新它的值，以及当键不在表中时将键存储到表的何处。
-
递归的二分查找rank()方法：
public int rank(Key key， int lo， int hi){ if (hi < lo) return lo; // 未查到到，返回插入的位置 int mid = lo + (hi - lo) / 2; int cmp = key.compareTo(Keys[mid]); if (cmp < 0) return rank(key， lo， mid-1); else if (cmp > 0) return rank(key， mid+1， hi); else return mid; } -
迭代的二分查找rank()方法：
public int rank(Key key){ int lo = 0， hi = N - 1; while (lo < hi){ int mid = lo + (hi - lo) / 2; int cmp = key.compareTo(keys[mid]); if (cmp < 0) hi = mid - 1; else if (cmp > 0) lo = mid + 1; else return mid; } return lo; } -
二分查找(基于有序数组)
public class BinarySearchST<Key extends Comparable<Key>， Value> { private Key[] keys; private Value[] vals; private int N; public BinarySearchST(int capacity) { keys = (Key[]) new Comparable[capacity]; vals = (Value[]) new Object[capacity]; } public int size() { return N; } public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); if (isEmpty()) return null; int i = rank(key); if (i < n && keys[i].compareTo(key) == 0) return vals[i]; return null; } public int rank(Key key) { } public void put(Key key， Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); int i = rank(key); // key is already in table if (i < N && keys[i].compareTo(key) == 0) { vals[i] = val; return; } for (int j = N; j > i; j--) { //将所有更大的键向后移动一格来腾出位置 keys[j] = keys[j-1]; vals[j] = vals[j-1]; } keys[i] = key; //并将给定的键值对分别插入到各自的合适位置 vals[i] = val; n++; } }在个键的有序数组中进行二分查找最多需要次比较（无论是否成功）；
二分查找虽然减少了比较的次数但无法减少运行的时间，因为：在键时随机排列的情况下，构造一个基于有序数组的符号表所需要访问数组的次数是数组长度的平方级别。
-
符号表的各种实现的优缺点：
使用的数据结构 实现 优点 缺点 链表（顺序查找） SequentialSearchST 适用于小型问题 对于大型符号表很慢 有序数组二分查找 BinarySearchST 最优的查找效率和空间需求，能够进行有序性相关的操作 插入操作很慢 二叉查找树 BST 实现简单，能够进行有序性相关的操作 没有性能上界的保证，链接需要额外的空间 平衡二叉查找树 RedBlackBST 最优的查找和插入效率，能够及逆行有序性相关的操作 链接需要额外的空间 散列表 SeparateChainHashST LInearProbingHashST 能够快速的查找和插入常见类型的数据 需要计算每种类型的数据的散列，无法进行相关性相关的操作，链接和空结点需要额外的空间
3.2 二叉查找树
-
一棵二叉查找树(BST)是一棵二叉树，其中每个结点都含有一个Comparable的键以及值，且每个结点的键都大于其左子树中的任意结点的键而小于其右子树的任意结点的键。
-
每个结点还会有一个结点计数器，它给出了以该结点为根的子树的结点总数
-
一棵二叉查找树代表了一组键的集合，而同一个集合可以用多颗不同的二叉查找树表示。如果将一棵二叉查找树的所有键按从左到右的顺序投影到一条直线上，那么会得到一条有序的键列。
public class BST<Key extends Comparable<Key>， Value>{ private Node root; //二叉查找树的根结点 private class Node{ private Key key; private Value val; private Node left， right; private int N; public Node(Key key， Value val， int N){ this.key = key; this.val = val; this.N = N; } } public int size(){ return size(root); } private int size(Node x){ if (x == null) return 0; else return x.N; } public Value get(Key key){} public void put(Key key， Value val){} } -
用递归的方法查找: 1️⃣ 如果树是空的，则查找未命中；2️⃣ 如果被查找的键和根结点的键相等，查找命中； 3️⃣ 如果被查找的键小于根结点的键，我们就递归地在左子树中查找；4️⃣ 如果被查找的键大于根结点的键，我们就递归地在右子树中查找。
-
插入：如果树是空的，就返回一个含有该键值对的新结点；如果被查找的键小于根结点的键，我们就继续在左子数中插入该键，否则在右子树中插入该键。
public Value get(Key key){ return get(root， key); } private Value get(Node x， Key key){ if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left， key); else if (cmp > 0) return get(x.right， key); else return x.val; } public void put(Key key， Value val){ root = put(rppt， key， val); } private Node put(Node x， Key key， Value val){ // 如果key存在于以x为根结点的子树中则更新它的值；否则以key和val为键值对的新结点插入到该子树中 if (x == null) return new Node(key， val， 1); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left， key， val); if (cmp > 0) x.right = put(x.right， key， val); else x.val = val; x.N = size(x.left) + size(x.right) + 1; return x; } -
递归调用前的代码想象成沿着树向下走，递归调用后的代码想象成沿着数上爬。
-
在由个随机键构造的二叉查找树中，查找命中平均所需的比较次数为(约)；插入操作和查找为未命中平均所需的比较次数为(约)。
-
如果根结点的左链接为空，那么一颗二叉查找树中最小的键就是根结点；如果根结点的左链接非空，那么树中的最小键就是左子树中的最小键；最大键类似。
-
如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键。大于等于key的最小键ceiling(key类似)。
public Key min(){ return min(root).key; } private Node min(Node x){ if (x.left == null) return x; return min(x.left); } public Key floor(Key key){ Node x = floor(root， key); if (x == null) return null; return x.key; } private Node floor(Node x， Key key){ if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp < 0) return floor(x.left， key); Node t = floor(x.right， key); if (t != null) return t; else return x; } -
排名也是递归实现的: 1️⃣ 如果给定的键和根结点的键相等，返回左子树的结点总数t；2️⃣ 如果给定的键小于根结点，返回该键在左子树中的排名；3️⃣ 如果给定的键大于根结点，返回t+1加上它在右子树中的排名。
/*二叉查找树中select()和rank()方法的实现*/ public Key select(int k){ return select(root， k).key; } private Node select(Node x， int k){ // 返回排名为K的结点 if (x == null) return null; int t = size(x.left); if (t > k) return select(x.left， k); else if (t < k) return select(x.right， k-t-1); else return x; } public int rank(Key key){ return rank（key， root); } private int rank(Key key， Node x){ // 返回以x为根结点的子树中小于x.key的键的数量 if (x == null) return 0; int cmp = key.compareTo(x.key); if (cmp < 0) return rank(key， x.left); else if (cmp > 0) return 1 + size(x.left) + rank(key， x.right); else return size(x.left); } -
删除操作通过将x替换为它的后继结点(其右子树中的最小结点)完成。1️⃣ 将指向即将被删除结点的链接保存为t; 2️⃣ 将x指向它的后继结点min(t.right); 3️⃣ 将x的右链接指向删掉后继结点的原右子树; 4️⃣ 将x的左链接设为t.left; 5️⃣修改结点计数器的值。
public void deleteMin() { root = deleteMin(root); } private Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); x.size = size(x.left) + size(x.right) + 1; return x; } public void deleteMax() { root = deleteMax(root); } private Node deleteMax(Node x) { if (x.right == null) return x.left; x.right = deleteMax(x.right); x.size = size(x.left) + size(x.right) + 1; return x; } public void delete(Key key) { root = delete(root， key); } private Node delete(Node x， Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) x.left = delete(x.left， key); else if (cmp > 0) x.right = delete(x.right， key); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; } -
使用中序遍历来进行范围查找，将符合条件的键放入一个队列，跳过不可能符合条件的子树。
public Iterable<Key> keys(){ return keys(min()， max()); } public Iterable<Key> keys(Key lo， Key hi){ Queue<Key> queue = new Queue<Key>(); keys(root， queue， lo， hi); return queue; } private void keys(Node x， Queue<Key> queue， Key lo， Key hi){ if (x == null) return; int cmplo = lo.compareTo(x.key); int cmphi = hi.compareTo(x.key); if (cmplo < 0) keys(x.left， queue， lo， hi); if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key); if (cmphi > 0) keys(x.right， queue， lo， hi); } -
在一棵二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。因此在某些场景下二叉查找树是不可接受的。
3.3 平衡查找树
-
2-3查找树:一棵2-3查找树或为一棵空树，或由以下结点组成：1️⃣ 2-结点:含有一个键和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。3️⃣ 3-结点:含有两个键和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
-
一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。
-
2-3树的查找：先将键和根结点中的键比较，如果它和其中任意一个相等，查找命中，否则根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找，如果是空链接则查找未命中.
-
2-3树的插入：2-3树应该在插入后继续保持平衡.我们先进行一次未命中的查找，1️⃣ 如果结束于2-结点，就将要插入的键保存在其中，把这个2结点替换为一个3结点；2️⃣ 如果结束于根3-结点，就临时将新键存入该结点，使之成为4-结点，再把中键变为根结点，最小键变为它的左子树，最大键变为它的右子树，树高加一；3️⃣ 如果结束于父结点为2-结点的3-结点，先使其成为4-结点，再把中键移动到父结点中，最小键变为它的左子树，最大键变为它的右子树；4️⃣ 如果结束于父结点为3-结点的3-结点，先使其成为4-结点，再把中间键插入到它的父结点中，此时父结点也为一个4-结点，在这个结点上进行相同的变换，一直向上直到遇到2-结点或根结点。
-
在一颗2-3树中分解一个4-结点的情况汇总：
-
2-3树是由下向上生长的，因为插入后始终保持平衡，所以即使在最坏情况下插入和查找的时间复杂度也为O(lgN)。2-3树的缺点是具有两种类型的结点，因此需要大量代码实现和维护，额外开销很大
-
**红黑二叉查找树(红黑树)**是用来实现2-3树的一种简单的数据结构。它的基本思想是用标准的二叉查找树和一些额外的信息来表示2-3树。树中的链接被分为两种类型：黑链接是普通链接，红链接将两个2-结点连接起来构成一个3结点。
-
将红链接画平时，一颗红黑树就是一颗2-3树。
-
红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树，满足这样定义的红黑树和相应的2-3树是一一对应的：1️⃣ 红链接均为左链接；2️⃣ 没有任何一个结点同时和两条红链接相连；3️⃣ 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
-
红黑树既是二叉查找树，也是2-3树(将由红链接相连的结点合并)，所以能够同时实现二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法。
-
旋转：如果出现了红色右链接或两条连续的红链接，就需要旋。.左旋转右链接也就是将两个键中较大者的左结点变为较小者的右结点，并将较大者作为根结点，较小者作为它的左结点。右旋转只需将左旋转中的左右对调即可。
/*左旋转h的右链接*/ Node rotateLeft(Node h){ Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; }/*右旋转h的左链接*/ Node rotateRight(Node h){ Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; x.N = h.N; h.N = 1 + size(h.left) + size(h.right); return x; } -
插入新键的几种情况：
1️⃣ 向单个2-结点或树底部的2-结点插入新键：如果新键小于老键，新增一个红链接的结点即可。如果新键大于老键，新增的结点会产生一条红色的右链接，将其左旋转。
2️⃣ 向3-结点插入大于两个键的新键：新键被连接到3-结点的右链接，直接将3-结点的两条链接都由红变黑，就得到了一棵由3个结点组成的平衡树。
3️⃣ 向3-结点插入小于两个键的新键：新键被连接到最左边的空链接，即产生了两条连续的红链接，只需将上层的红链接右旋转即可变为情况2。
4️⃣ 向3-结点插入介于两个键之间的新键：此时产生一左一右两条连续的红链接，只需将下层的红链接左旋转即可变为情况3。
-
颜色转换：用于将子结点的颜色由红变黑，父结点的颜色由黑变红。
void flipColors(Node h){ h.color =RED; h.left.color = BLACK; h.right.color = BLACK; } -
每次插入后都要将根结点设为黑色， 当根结点由红变黑时树的黑链接高度加1。
-
插入:
-
如果右子结点是红色的而左子结点是黑色的，进行左旋转
-
如果左子结点是红色的且它的左子结点也是红色的，进行右旋转
-
如果左右子结点均为红色，进行颜色转换
-
不断地将红链接由中间键传递给父结点，直至遇到一个2-结点或根结点时，插入就完成了
public class RedBlackBST<Key extends Comparable<Key>， Value>{ private Node root; public void put(Key key， Value val){ root = put(root， key， val); root.color = BLACK; } private Node put(Node h， Key key， Value val){ if (h==null){return new Node(key， val， 1， RED);} int cmp = key.compareTo(h.key); if (cmp < 0) h.left = put(h.left， key， val); else if (cmp > 0) h.right = put(h.right， key， val); else h.val = val; if (isRed(h.right) && ! isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.N = size(h.left) + size(h.right) + 1; retrun h; } }
- 红黑树查找，插入，删除和范围查询的时间复杂度在最坏情况下都为O(lgN)
3.4散列表
-
使用散列表的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引，第二步是处理碰撞冲突(多个键散列到相同索引值的情况)。
-
常用散列方法：1️⃣ 正整数：散列最常用的方法是除留余数法。选择大小为素数M的数组，对于任意正整数k，计算k除以M的余数；2️⃣ 浮点数：表示为二进制数然后再使用除留余数法；3️⃣ 字符串：将每位字符表示为一个整数，然后一个比任何字符的值都大的数R来将字符串转化为一个R进制值，再在每一步用除留余数法； 4️⃣ 组合键:类似于字符串，将组合值用R进制表示并在每一步用除留余数法。
-
Java 令所有数据类型都继承了一个能够返回一个32比特整数的hashCode( )方法。如果两个对象的hashCode( )方法返回值不同，那么这两个对象是不同的。但如果两个对象的hashCode( ) 方法返回值相同，这两个对象也可能不同，还需要用**equals( )**方法判断。
-
拉链法：将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。基本思想是选择足够大的M，使得所有链表都尽可能短。查找分两步：1️⃣ 根据散列值找到对应的链表；2️⃣ 沿着链表顺序查找相应的键。
public class SeparateChainingHashST<Key， Value>{ private int N; //键值对总数 private int M; //散列表大小 private SequentialSearchST<Key， Value>[] st; //存放链表对象的数组； public SeparateChainingHashST(){ this(997); } public SeparateChainingHashST(int M){ this.M = M; //创建M条链表； st = (SequentialSearchST<Key，Value>[]) new SequentialSearchST[M]; for (int i = 0; i < M; i++) st[i] = new SequentialSearchST(); } private int hash(Key key){ return (key.hashCode() & 0x7fffffff) % M;)//屏蔽符号位，32位整数变为32位非负整数 } public Value get(Key key){ return (Value) st[hash(key)].get(key); } public void put(Key key， Value val){ st[hash(key)].put(key， val); } } -
在一张含有M条链表和N个键的散列表中，未命中查找和插入的时间复杂度是O(N/M)。
-
散列后键的顺序信息丢失了。所以散列表不适合用来寻找最值或范围查找。
-
依靠数组中的空位解决碰撞冲突的方法叫开放地址散列表。其中最简单的是线性探测法：当碰撞发生时，检查散列表中的下一个位置，直到命中或遇到空元素为止。
public class LinearProbingHashST<Key， Value>{ private int N; //符号表中键值对的总数 private int M = 16; //线性探测表的大小； private Key[] keys; //键 private Value[] vals; //值 public LinearProbingHashST(){ keys = (Key[]) new Object[M]; vals = (Value[]) new Object[M]; } private int hash(Key key){ return (key.hashCode() & 0x7fffffff) % M; // 去除符号位 } public void put(key key， Value val){ if (N >= M/2) resize(2*M); int i; for (i = hash(key); keys[i] != null; i = (i+1)%M) if (keys[i].equals(keys=)) {vals[i] = val; return;} //存在就更新 keys[i] = key; vals[i] = val; //不存在就插入 N++; } public Value get(Key key){ for (int i = hash(key); keys[i] != null; i=(i+1) % M){ if (keys[i].equals(key)) return vals[i]; return null; } } } -
当散列表快满时查找所需的探测次数是巨大的，但当使用率 小于 1/2 时探测的预计次数只在1.5到2.5之间。
-
开放地址散列表的删除除了将该键所在位置置为null，还需要将被删除键右侧的所有键重新插入散列表，以防之后的元素无法被查找。
public void delete(Key key){ if (!contains(key)) return; int i = hash(key); while (!key.equals(keys[i])) i = (i+1) % M; keys[i] = null; vals[i] = null; i = (i+1) % M; while (keys[i] != null){ Key keyToRedo = keys[i]; Value valToRedo = vals[i]; keys[i] = null; vals[i] = null; N--; put(keyToRedo， valToRedo); i = (i+1) % M; } N--; if (N > 0 && N == M/8) resize(M/2); } -
元素在数组中聚集成的一组连续的条目叫键簇，为了保证性能，应该使键簇尽可能短小。可以证明数组的使用率应该在1/8~1/2之间，所以在每次插入元素前和删除元素后都需动态调整大小。
-
问：为什么不将 hash(x) 实现为 x.hashCode( ) % M ?
答：散列值必须在0到M-1之间，而在Java中，取余(%)的结果可能是负数；如果用 **Math.abs( )**对于最大的整数会返回一个负值。
3.5 应用
-
各种符号表实现的渐进性能的总结
-
相对于二叉查找树，散列表的优点是代码更简单，且查找时间最优。二叉查找树相对于散列表的优点在于抽象结构更简单，红黑树可以保证最坏情况下的性能且支持的操作更多（如排名、选择、排序和范围查找）。
-
使用put操作构造一张符号表以备get查询，这种应用叫做字典
- 一个键和多个值相关联的符号表叫做索引。用值来查找键的操作叫做反向索引.
- 使用散列表表示稀疏矩阵可以大大提高矩阵与向量相乘的效率。它所需的时间和N+非零元素成正比，而用数组表示的话则为$N^2 $ ，N为矩阵的尺寸。
chapter 4 图
4.1 无向图
- 图是由一组顶点和一组能够将两个顶点相连的边组成的，一般用0至V-1表示一张含有V个顶点的图中的各个顶点，用v-w或w-v表示连接v和w的边。边仅仅是两个顶点之间的连接的图称为无向图。
- 一条连接一个顶点和其自身的边称为自环。连接同一对顶点的两条边称为平行边。一般将含有平行边的图称为多重图，将没有平行边或自环的图称为简单图。
- 某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集组成的图。
- 路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。
- 环是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含有重复顶点和边的环。
- 如果从任意一个顶点都存在一条路径到达另一个任意顶点，那么这幅图是连通图。
- 图的密度是指已经连接的顶点对斩所有可能被连接的顶点对的比例，由此分出稀疏图和稠密图。
- 二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。
- 一般采用邻接表数组来表示图。它将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中。它使用的空间和V+E成正比。添加一条边所需的时间为常数。遍历顶点v的所有相邻顶点所需的时间和v的度数成正比。
- 深度优先搜索(DFS)是搜索连通图的经典递归算法，所需的时间和顶点的度数之和成正比。使用的是栈:
- 在访问其中一个顶点时将它标记为已访问
- 递归地访问该顶点的所有没有被标记过的邻居顶点
- 广度优先搜索(BFS)是解决单点最短路径的经典算法，它所需的时间在最坏情况下和V+E成正比。使用的是队列，先将起点加入队列，重复以下步骤直到队列为空:
- 将与v相邻的所有未被标记过的顶点加入队列，删除v
- 取队列中的下一个顶点v并标记它
- DFS和BFS的区别在于DFS总是获取最晚加入的顶点，而BFS总是获取最早加入的结点。
- DFS更适合实现图的抽象数据类型，因为它能更有效地利用已有的数据结构。而union-find算法适合于只需要判断连通性的任务。
- 利用一个符号表保存字符和索引，一个数组保存反向索引和一张图就可以实现符号图。
4.2 有向图
- 一幅有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。在有向图中，一个顶点的出度为由该顶点指出的边的总数;一个顶点的入度为指向该顶点的边的总数。用v→w表示有向图中一条由v指向w的边。
- 有向路径由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。有向环为一条至少含有一条边且起点和终点相同的有向路径。简单有向环是一条不含有重复的顶点和边的环。
- 和无向图类似，一般使用邻接表来表示有向图，用顶点v所对应的邻接链表中包含一个w顶点来表示边v→w。每条边都只会在其中出现一次。DFS和BFS同样可用于有向图。
- 拓扑排序:给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。即有优先级限制下的调度问题。当且仅当一幅有向图是无环图时它才能进行拓扑排序。
- 有向无环图(DAG)是一幅不含有环的有向图。想要进行有向环检测，可以基于DFS，一旦找到一条边v→w且w已经存在于栈中，就找到了一个环。
- DFS遍历一幅图以后，有以下三种排列顺序:
- 前序:在递归调用之前将顶点加入队列，即dfs()的调用顺序
- 后序:在递归调用之后将顶点加入队列，即顶点遍历完成的顺序
- 逆后序:在递归调用之后将顶点压入栈，即这幅图的拓扑排序(如果是有向无环图)
- 如果两个顶点v和w是互相可达的，则称它们为强连通的。如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的。两个顶点是强连通的当且仅当它们都在一个普通的有向环中。
- 通常用Kosaraju算法来计算强连通分量:
- 在给定的一幅有向图G中，计算它的反向图的逆后序排列
- 在G中进行DFS，但是要按照1得到的顺序来访问所有未被标记的顶点
- 所有在同一个递归DFS调用中被访问到的顶点都在同一个强连通分量中
4.3 最小生成树
- 加权图是一种为每条边关联一个权值或是成本的图模型。
- 图的生成树是它的一棵含有其所有顶点的无环连通子图。一幅加权无向图的**最小生成树(MST)**是它的一棵权值最小的生成树。
- 在计算最小生成树时，做以下约定:
- 只考虑连通图
- 边的权重不一定表示距离
- 边的权重可能是0或者负数
- 所有边的权重都各不相同
- 树的两个重要性质:
- 用一条边连接树中的任意两个顶点都会产生一个新的环
- 从树中删去一条边将会得到两颗独立的树
- 图的一种切分是将图的所有顶点分为两个非空且不重复的两个集合。横切边是一条连接两个属于不同集合的顶点的边。
- 切分定理:在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。
- 切分定理是解决最小生成树问题的所有算法的基础。这些算法都是一种贪心算法的特殊情况。即找到一种切分，它产生的横切边均不为黑色，将它权重最小的横切边标记为黑色，直到标记了V-1条黑色边为止。不同之处在于保存切分和判定权重最小的横切边的方式。
- 同样可以使用邻接表来表示加权无向图，只需要增加一个权重域。
- Prim算法:
- 一开始最小生成树只有一个顶点，然后会向它添加V-1条边。每次总是将下一条连接树顶点与非树顶点且权重最小的边加入树中。每一步总是为一棵树添加一条边。
- 使用优先队列来根据权重比较所有边
- 分为延时实现和即时实现。区别在于是否立即删除失效的横切边(即连接新加入的顶点和树中已有顶点之间的边)。
- 延时实现所需空间与E成正比，所需时间与ElogE成正比。
- 即时实现不仅删除失效的边，而是仅保存非树顶点到树顶点的边中权重最小的那条，并在每次加入新顶点后检查是否需要更新。所需空间与V成正比，时间与ElogV成正比。
- Kruskal算法:
- 按照边的权重顺序处理它们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，直到树中含有V-1条边为止。每一步总是连接森林中的两棵树(包括单顶点树)。
- 在实现中，使用优先队列来将边按照权重排序，使用union-find来识别会形成环的边，以及一条队列来保存最小生成树的所有边。
- 所需空间与E成正比，所需时间与ElogE成正比。
4.4 最短路径
- 在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。
- **最短路径树(SPT)**包含了顶点s到所有可达的顶点的最短路径
- 边v->w的松弛是指检查从顶点s到w的最短路径是否是先从s到v，然后再由v到w，即。如果是，则更新，如果不是，则称这条边失效了。
- 顶点的松弛是指对该顶点指出的所有边进行松弛。
- 最优性条件:当且仅当对于从v到w的任意一条边e，这些值都满足distTo[w]<=distTo[v]+e。weight()时它们是最短路径的长度。这证明了判断是否为最短路径的全局条件与松弛时检测的局部条件是等价的。
- 通用最短路径算法:放松图中的任意边，直到不存在有效边为止。
- Dijkstra算法(注意只能解决正权重的加权有向图中的最短路径问题):
- 首先将distTo[s]初始化为0，distTo[]中的其他元素初始化为起点s到该顶点的距离，注意如果不相邻则为正无穷。
- 然后将distTo[]最小的非树顶点松弛并加入树中
- 重复2，直到所有的顶点都在树中或者所有的非树顶点的distTo[]值均为无穷大。
-
按照拓扑顺序放松顶点，就能在和E+V成正比的时间内解决无环加权有向图的单点最短路径问题。同理，要解决无环加权有向图的最长路径问题，只需将原图中所有边的权重变为负值，再求最短路径即可。
-
当且仅当加权有向图中至少存在一条从s到v的有向路径且该路径上的任意顶点都不存在于任何负权重环中时，s到v的最短路径才是存在的。
-
数据结构--Dijkstra算法最清楚的讲解 https://blog.csdn.net/heroacool/article/details/51014824
-
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止
基本思想
-
通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
-
初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。
操作步骤：1️⃣ 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。2️⃣ 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。3️⃣ 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。4️⃣ 重复步骤(2)和(3)，直到遍历完所有顶点。
#dijkstra算法实现，有向图和路由的源点作为函数的输入，最短路径最为输出
def dijkstra(graph,src):
# 判断图是否为空，如果为空直接退出
if graph is None:
return None
nodes = [i for i in range(len(graph))] # 获取图中所有节点
visited=[] # 表示已经路由到最短路径的节点集合
if src in nodes:
visited.append(src)
nodes.remove(src)
else:
return None
distance={src:0} # 记录源节点到各个节点的距离
for i in nodes:
distance[i]=graph[src][i] # 初始化
# print(distance)
path={src:{src:[]}} # 记录源节点到每个节点的路径
k=pre=src
while nodes:
mid_distance=float('inf')
for v in visited:
for d in nodes:
new_distance = graph[src][v]+graph[v][d]
if new_distance < mid_distance:
mid_distance=new_distance
graph[src][d]=new_distance # 进行距离更新
k=d
pre=v
distance[k]=mid_distance # 最短路径
path[src][k]=[i for i in path[src][pre]]
path[src][k].append(k)
# 更新两个节点集合
visited.append(k)
nodes.remove(k)
print(visited,nodes) # 输出节点的添加过程
return distance,path
if __name__ == '__main__':
graph_list = [ [0, 2, 1, 4, 5, 1],
[1, 0, 4, 2, 3, 4],
[2, 1, 0, 1, 2, 4],
[3, 5, 2, 0, 3, 3],
[2, 4, 3, 4, 0, 1],
[3, 4, 7, 3, 1, 0]]
distance,path= dijkstra(graph_list, 0) # 查找从源点0开始带其他节点的最短路径
print(distance,path)
- Bellman-Ford算法:
- 在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，可以解决其中的单点最短路径问题
- 将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大，以任意顺序放松有向图的所有边，重复V-1轮
- 算法所需的时间和EV成正比，空间和V成正比。
- 套汇问题等价于加权有向图中的负权重环的检测问题。
chapter 5 字符串
5.1 字符串排序
-
在Java中，String类型的**length( )**方法实现了获取字符串的长度的操作。**substring( )**方法实现了提取特定的子字符串的操作。
-
字符串排序方法可以分为从右到左检查键中的字符的低位优先(LSD)和从左到右检查键中字符的高位优先(MSD)。
-
键索引计数法是一种适用于小整数键的简单排序方法，它要求数组a[]中的每个元素都保存一个字符串和一个组号，原来元素是依据字符串排列的，现在希望按组号排列，在组内保持原顺序.键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组11N+4R+1次。
-
键索引计数法步骤：1️⃣ 频率统计：使用一个数组count[]计算每个键出现的频率。如果键为r，就将count[r+1]加1。2️⃣ 将频率转换为索引：任意给定的键的起始索引均为所有较小的键所对应的出现频率之和，只需循环count[r+1]+=count[r]这个语句即可转换出一张索引表。3️⃣ 数据分类：有了索引表后，将所有元素移动到一个辅助数组aux[]中进行排序。每次移动后将count[]中对应元素的值加1，这保证了这种排序的稳定性。4️⃣ 回写：将排序结果复制回原数组中。
int N = a.length; String[] aux = new String[N]; int[] count = new int[R+1]; // 计算出现频率 for (int i = 0; i < N; i++) count[a[i].key() + 1]++; //将频率转换为索引 for (int r = 0; r < R; r++) count[r+1] += count[r]; //将元素分类 for (int i = 0; i < N; i++) aux[count[a[i].key()]++] = a[i]; //回写 for (int i = 0; i < N; i++) a[i] = aux[i]; -
低位优先的字符串排序(LSD)：将等长字符串(假设长度为W)排序可以通过从右向左以每个位置的字符作为键，用键索引计数法将字符串排序W次实现。这依赖于键索引计数法的稳定性。对于基于R个字符的字母表的N个以长为W的字符串为键的元素，LSD需要访问~7WN+3WR次数组。因为实际中R<<N，因此LSD算法的时间是O(WN)。
public class LSD{ public static void sort(String[] a, int w){ // 通过前W个字符将a[]排序 int N = a.length; int R = 256; String[] aux = new String[N]; for (int d = w-1; d >= 0; d--){ int[] count = new int[R+1]; //根据第d个字符用键索引计数法排序 for (int i = 0; i < N; i++) count[a[i].charAt(d) + 1]++; // 计算出现频率 for (int r = 0; r < R; r++) count[r+1] += count[r]; //将频率转换为索引 for (int i = 0; i < N; i++) aux[count[a[i].charAt(d)]++] = a[i]; //将元素分类 for (int i = 0; i < N; i++) a[i] = aux[i]; //回写 } } } -
高位优先的字符串排序(MSD)：首先用键索引计数法将所有字符串按照首字母排序，然后再递归地将每个首字母所对应的子数组排序(忽略首字母)。对于MSD来说，将小数组切换到插入排序对于高位优先的字符串排序算法是必须的，另外它无法很好的处理等值键。对于基于R个字符的字母表的N个平均长度为w的字符串，MSD需要访问8N+3R到7wN+3wR之间次数组。
public class MSD{ private static int R = 256; private static final int M = 15; //小数组的切换阈值 private static String[] aux; private static int charAt(String s,int d){ if (d < s.lengtg()) return s.charAt(d);else return -1; } public static void sort(String[] a){ int N = a.length; aux = new String[N]; sort(a, 0, N-1, 0); } private static void sort(String[] a, int lo, int hi, int d){ //以第d个字符为键将a[lo]至a[hi]排序 if (hi <= lo + M){ Insertion.sort(a, lo, hi, d); return; } int[] count = new int[R+2]; for (int i = lo; i <= hi; i++) count[charAt(a[i], d) + 2]++; for (int r = 0; r < R+1; r++) count[r+1] += count[r]; for (int i = lo; i <= hi; i++) aux[count[charAt(a[i], d) + 1]++] = a[i]; for (int i = lo; i <= hi; i++) a[i] = aux[i - lo]; for (int r = 0; r < R; r++) sort(a, lo+count[r], lo+count[r+1]-1, d+1); } } -
三向字符串快速排序:根据键的首字母进行三向切分，仅在中间子数组的中的下一个字符继续递归排序.它能够很好地处理等值键，有较长公共前缀的键，取值范围较小的键和小数组.另外它不需要额外的空间.
5.2 单词查找树
- 单词查找树(trie树)的每个结点都有R条链接，R为字母表的大小。但是一般其中都含有大量的空链接，可以被忽略。每条链接都对应着一个字符，每个键所关联的值保存在该键的最后一个字母所对应的结点中。
- 查找给定字符串键所对应的值的方式就是从根结点开始检查某条路径上的所有结点，这意味着到达树中表示尾字符的结点或者一个空链接。插入之前需要先进行一次查找，如果遇到了空链接则为键中还未被检查的每个字符创建一个对应结点，如果到达了尾字符结点则将该结点的值设为要插入的键所对应的值。
- 单词查找树的结点是一个值和大小为R的数组构成的。将基于含有R个字符的字母表的单词查找树称为R向单词查找树。
- 可以用递归的方法查找所有键，方法的参数是结点和该结点关联的字符串。如果一个结点的值非空，就将它相关联的字符串加入队列，然后递归访问它的链接数组所指向的所有可能的字符结点。
- 要删除一个键值对，先找到键所对应的结点并将它的值设为空，如果它有指向子结点的非空链接则删除结束，如果它的所有链接均为空就从数据结构中删去这个结点，再检查它的父结点的所有链接是否为空。
- 对于任意给定的一组键，单词查找树都是唯一的。查找需要访问数组的次数最多是键的长度加1。未命中查找平均所需检查的结点数量为(logR)N。树中的链接总数在RN到RNw之间。
- 三向单词查找树:用来避免R向单词查找树过度的空间消耗.每个结点都含有一个字符，三条链接和一个值。三条链接对应着当前字母小于，等于和大于结点字母的所有键。所需的空间在3N到3Nw之间。查找未命中平均需要比较字符~lnN次。
5.3 子字符串查找
- 子字符串查找问题：给定一段长度为N的文本和一个长度为M的模式字符串，在文本中找到一个和该模式相符的子字符串。一般来说M相对于N是很小的。
- 暴力子字符串查找算法就是遍历文本字符串，如果某字符和模式的第一个字符匹配则移动指向模式的指针，否则移动指向文本的指针。这种方法在最坏情况下需要**~NM**次字符比较(例如二进制文本)。
- KMP子字符串查找算法(注:书中用确定有限状态自动机DFA的思想来讲解，个人感觉不好理解，本文用了大一学数据结构时的解释方法):
- 基本思想:当出现不匹配时，就能知晓一部分文本的内容，可以利用这些信息避免将指针回退到所有已知字符之前。
- 预处理:根据模式计算出一个转移数组next[].其中next[0]=-1，next[1]=0，next[j]表示模式字符串中第0位到第j-1位中相同的最长前缀和最长后缀的长度。next数组可以用模式匹配的思想编程得到。
- 发生不匹配:目标串的指针不变，若next[j]>=0，则将模式字符串右移j-next[j]位个字符，用模式的第next[j]个字符与文本的第i个字符比较.若next[j]=-1，则将模式字符串右移j+1个字符，用第0个字符与文本的第i+1个字符比较。
- 优化:如果根据next数组回退之后的位置的字符和现有字符相同，则必定是不匹配，仍要继续回退，因此建立nextval数组，将重复字符的回退位置都设为第一个该字符的回退位置.
- KMP算法适用于在重复性很高的文本中查找重复性很高的模式，它访问的字符不会超过M+N个.
- Boyer-Morre字符串查找算法:
- 使用数组right[]记录字母表中的每个字符在模式中出现的最靠右的地方，不存在则为-1.含义是如果该字符出现在文本中且在查找时造成了一次匹配失败，模式应该向右跳跃多远.
- 如果造成匹配失败的字符不包含在模式中，则将模式字符串向右移动j+1个位置
- 如果包含在模式字符串中，则将模式向右移动j-right['char']
- 如果这种方式无法增大i，就将i加1
- 一般情况下，Boyer-Moore需要**~N/M**次字符比较.
- Rabin-Karp指纹字符串查找算法:
- 基本思想:这是一种基于散列的算法.长度为M的字符串对应着一个R进制的M位数，将该数除以一个随机的素数Q并取余就可以将它保存在大小为Q的散列表中.
- 计算散列函数:在文本中将子字符串右移一位，对应的M位数操作就是将它减去第一个数字的值，乘上R，再加上最后一个数字的值.又因为在每次算数操作之后取余等价于在所有算数操作完成后取余，因此只需对上述操作的每一步先取余就可以得到下一位的子字符串的散列值.
- 技巧:为了避免有多个子字符串有相同散列值，可以将Q设为一个大于1020的值，这样冲突的概率将小于10-20.
5.4 正则表达式
- 正则表达式就是按照某种模式进行字符匹配的表达式。书中使用语言指代一个字符串的集合.模式的描述由连接，或(|)，**闭包(*)**三种基本操作构成。
- 字符集描述集用于简化正则表达式
- 闭包的简写
- .|*()是用来构造正则表达式的元字符，因此要用\开头的转义字符来表示
- 正则表达式模拟匹配程序的总体结构是:构造和给定正则表达式相对应的非确定有限状态自动机(NFA)，模拟NFA在给定文本上的运行轨迹.
- NFA有以下特点:
- 长度为M的正则表达式中的每个字符在对应NFA中有且只有一个对应状态，NFA起始状态为0，并有一个虚拟的接受状态M
- 字母表中的字符所对应的状态都有一条指向模式中的下一个字符对应状态的黑边.
- 元字符所对应的状态至少有一条指出的红边，可能指向任意状态
- NFA的状态转换:
- 匹配转换:如果文本中的当前字符和当前字母表中的字符匹配，NFA可以扫过文本中的字符并由黑边转换到下一个状态
- ε转换:NFA可以通过红边转换到另一个状态而不扫描文本中的字符
- 使用长度为M+1的数组来保存正则表达式本身，这个数组也表示了匹配转换.使用有向图来表示ε转换.首先查找所有从状态0通过ε转换可达的状态来初始化可达性集合，然后如果有字符匹配了集合中的状态，就将集合改为这个字符通过匹配转换后到达的状态，再加上这些状态通过ε转换可达的状态.
- 判定一个长度为M的正则表达式所对应的NFA能否识别一段长度为N的文本所需的时间在最坏情况下和NM成正比.构造对应的NFA所需的时间和空间在最坏情况下与M成正比
5.5 数据压缩
- 现代计算机系统中的所有类型的数据都是用二进制表示的.用比特流表示比特的序列，用字节流表示可以看作固定大小的字节序列的比特序列.
- 数据压缩的基础模型由压缩盒(将比特流B转化为压缩版本C(B))和展开盒(将C(B)转化回B)组成，用|B|表示比特流中比特的数量，则C(B)/|B||称为压缩率.这种模型叫做无损压缩模型.常用于数值数据或可执行代码的压缩.
- 不存在能够压缩任意比特流的算法，因此无损压缩算法必须尽量利用被压缩的数据流中的已知结构(小规模字母表，较长的连续相同的位或字符，频繁使用的字符，较长的连续重复的位或字符).
- **游程编码(RLE)**的基本原理是用长度代替具有相同值的连续符号，连续符号构成了一段连续"游程".适用于含有较长游程的数据，比如高分辨率的位图.
- 霍夫曼压缩的思想是用较少的比特表示出现较频繁的字符，它是一种前缀码(所有字符编码都不会成为其他字符编码的前缀).构造霍夫曼树的过程是:先找到频率最小的两个结点，然后创造一个以两者为子结点且频率为两者之和的新结点，不断重复这个过程知道所有结点被合并为一棵单词查找树.
- LZW压缩算法是为变长模式生成一张定长的符号表:
- 找出未处理的输入在符号表中最长的前缀字符串s
- 输出s的编码
- 继续扫描s之后的一个字符c
- 在符号表中将s+c的值设为下一个编码值
支付宝 
微信