[数据结构][算法][面向对象][Java]
1 设计接口
1.1 容器接口Container
package ds; import java.util.NoSuchElementException; public interface Container{ int size(); default boolean isEmpty(){ return size() == 0; } default void notEmptyCheck() { if (isEmpty()) { throw new NoSuchElementException("size == 0"); } } }
1.2 背包接口Bag
package ds; public interface Bag<T> extends Container { void add(T data); }
1.3 栈接口Stack
package ds; public interface Stack<T>extends Container { void push(T data); T pop(); T peek(); }
1.4 队列接口Queue
package ds; public interface Queue<T> extends Container { T peek(); void enqueue(T data); T dequeue(); }
1.5 Union-Find算法接口UF
package ds; public interface UF { int size(); int find(int p); boolean connected(int p, int q); void union(int p, int q); default void validate(int p, int n) { if (p < 0 || p >= n) { throw new IllegalArgumentException("p>=0 && p<n"); } } }
2 实现接口
为数组和链表定义了公共的结点和迭代器实现。
2.1 结点类Node
package ds.util; public class Node<T> { public T data; public Node<T> next; }
2.2 数组迭代器ArrayIterator
package ds.util; import java.util.Iterator; import java.util.NoSuchElementException; public class ArrayIterator<T> implements Iterator<T> { private int i; private final int size; private final T[] array; public ArrayIterator(T[] array, int size) { this.array = array; this.size = size; } @Override public boolean hasNext() { return i < size; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return array[i++]; } }
2.3 链表迭代器ListIterator
package ds.util; import java.util.Iterator; import java.util.NoSuchElementException; public class ListIterator<T> implements Iterator<T> { private Node<T> current; public ListIterator(Node<T> first) { current = first; } @Override public boolean hasNext() { return current != null; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } T result = current.data; current = current.next; return result; } }
2.4 背包(Bag)的实现
背包(Bag)是一种不支持从中删除元素的集合数据类型。
2.4.1 能动态调整数组大小的Bag
package ds.impl; import ds.Bag; import java.util.Iterator; import ds.util.ArrayIterator; public class ArrayBag<T> implements Iterable<T>,Bag<T> { private T[] array; private int size; public ArrayBag() { array = (T[]) new Object[2]; size = 0; } @Override public int size() { return size; } @Override public void add(T data) { if (size == array.length) { resize(2 * array.length); } array[size++] = data; } private void resize(int capacity) { assert capacity >= 0; T[] tmp = (T[]) new Object[capacity]; System.arraycopy(array, 0, tmp, 0, size); array = tmp; } @Override public Iterator<T> iterator() { return new ArrayIterator(array,size); } }
2.4.2 链式Bag的实现
package ds.impl; import ds.util.Node; import ds.Bag; import java.util.Iterator; import ds.util.ListIterator; public class LinkedBag<T> implements Iterable<T>, Bag<T> { private Node<T> first; private int size; public LinkedBag() { first = null; size = 0; } @Override public int size() { return size; } @Override public void add(T data) { Node<T> old = first; first = new Node<>(); first.data = data; first.next = old; size++; } @Override public String toString() { StringBuilder s = new StringBuilder(); for (T data : this) { s.append(data).append(' '); } return s.toString(); } @Override public Iterator<T> iterator() { return new ListIterator(first); } }
2.5 栈(Stack)的实现
栈(Stack)是一种先进后出的数据类型。
2.5.1 能动态调整数组大小的Stack
package ds.impl; import ds.Stack; import java.util.Iterator; import ds.util.ArrayIterator; public class ArrayStack<T> implements Iterable<T>,Stack<T> { private T[] array; private int size; public ArrayStack(){ array = (T[]) new Object[2]; size = 0; } @Override public Iterator<T> iterator() { return new ArrayIterator(array,size); } @Override public int size() { return size; } @Override public void push(T data) { if(size == array.length){ resize(2* array.length); } array[size++] = data; } private void resize(int capacity) { assert capacity >= size; T[] tmp = (T[]) new Object[capacity]; System.arraycopy(array, 0, tmp, 0, size); array = tmp; } @Override public T pop() { notEmptyCheck(); T result = array[size-1]; array[size-1] = null; size--; if(size>0 && size == array.length/4){ resize(array.length/2); } return result; } @Override public T peek() { notEmptyCheck(); return array[size-1]; } }
2.5.2 链式Stack的实现
package ds.impl; import ds.util.Node; import ds.Stack; import java.util.Iterator; import ds.util.ListIterator; public class LinkedStack<T> implements Iterable<T>,Stack<T> { private Node<T> first; private int size; public LinkedStack() { first = null; size = 0; } @Override public int size() { return size; } /** * 向栈中推入一个新元素 * * @param data 新元素 */ @Override public void push(T data) { Node<T> oldFirst = first; first = new Node<>(); first.data = data; first.next = oldFirst; size++; } /** * 从栈中弹出栈首元素 * * @return 栈首元素 */ @Override public T pop() { notEmptyCheck(); T result = first.data; first = first.next; size--; return result; } /** * 查看栈首元素 * @return 栈首元素 */ @Override public T peek() { notEmptyCheck(); return first.data; } @Override public String toString() { StringBuilder s = new StringBuilder(); for (T data : this) { s.append(data).append(' '); } return s.toString(); } @Override public Iterator<T> iterator() { return new ListIterator(first); } }
2.6 队列(Queue)的实现
队列(Queue)是一种先进先出的数据类型。
2.6.1 能动态调整数组大小的Queue
package ds.impl; import ds.Queue; import java.util.Iterator; public class ArrayQueue<T> implements Iterable<T>,Queue<T> { private T[] array; private int size; private int first; private int last; public ArrayQueue() { array = (T[]) new Object[2]; size = 0; first = 0; last = 0; } @Override public int size() { return size; } @Override public void enqueue(T data) { if (size == array.length) { resize(2 * array.length); } array[last++] = data; if (last == array.length) { last = 0; } size++; } @Override public T dequeue() { notEmptyCheck(); T result = array[first]; array[first] = null; size--; first++; if (first == array.length) { first = 0; } if (size > 0 && size == array.length / 4) { resize(array.length / 2); } return result; } @Override public T peek(){ notEmptyCheck(); return array[first]; } private void resize(int capacity) { assert capacity >= size; T[] tmp = (T[]) new Object[capacity]; for (int i = 0; i < size; i++) { tmp[i] = array[(first + i) % array.length]; } array = tmp; first = 0; last = size; } @Override public Iterator<T> iterator() { return new ds.util.ArrayIterator(array,size); } }
2.6.2 链式Queue的实现
package ds.impl; import ds.util.Node; import ds.Queue; import java.util.Iterator; import ds.util.ListIterator; public class LinkedQueue<T> implements Iterable<T>, Queue<T> { private Node<T> first; private Node<T> last; private int size; public LinkedQueue() { first = null; last = null; size = 0; } @Override public int size() { return size; } @Override public T peek() { notEmptyCheck(); return first.data; } @Override public void enqueue(T data) { Node<T> oldLast = last; last = new Node<>(); last.data = data; last.next = null; if (isEmpty()) { first = last; } else { oldLast.next = last; } size++; } @Override public T dequeue() { notEmptyCheck(); T result = first.data; first = first.next; size--; if (isEmpty()) { last = null; } return result; } @Override public String toString() { StringBuilder s = new StringBuilder(); for (T data : this) { s.append(data).append(' '); } return s.toString(); } @Override public Iterator<T> iterator() { return new ListIterator(first); } }
2.7 Union-Find算法的实现
并查集(Union-Find)是解决动态连通性问题的一类非常高效的数据结构。
2.7.1 DefaultUF
package ds.impl; import ds.UF; public class DefaultUF implements UF { private int[] parent; private byte[] rank; private int size; public DefaultUF(int n) { if (n < 0) { throw new IllegalArgumentException(); } size = n; parent = new int[n]; rank = new byte[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } } @Override public int find(int p) { validate(p, parent.length); while (p != parent[p]) { parent[p] = parent[parent[p]]; p = parent[p]; } return p; } @Override public int size() { return size; } @Override public boolean connected(int p, int q) { return find(p) == find(q); } @Override public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) { return; } if (rank[rootP] < rank[rootQ]) { parent[rootP] = rootQ; } else if (rank[rootQ] > rank[rootP]) { parent[rootQ] = rootP; } else { parent[rootQ] = rootP; rank[rootP]++; } size--; } }
2.7.2 QuickFindUF
package ds.impl; import ds.UF; public class QuickFindUF implements UF { private final int[] id; private int size; public QuickFindUF(int n) { size = n; id = new int[n]; for (int i = 0; i < n; i++) { id[i] = i; } } @Override public int size() { return size; } @Override public int find(int p) { validate(p, id.length); return id[p]; } @Override public boolean connected(int p, int q) { validate(p, id.length); validate(q, id.length); return id[p] == id[q]; } @Override public void union(int p, int q) { validate(p, id.length); validate(q, id.length); int pID = id[p]; int qID = id[q]; if (pID == qID) { return; } for (int i = 0; i < id.length; i++) { if (id[i] == pID) { id[i] = qID; } } size--; } }
2.7.3 QuickUnionUF
package ds.impl; import ds.UF; public class QuickUnionUF implements UF { private final int[] parent; private int size; public QuickUnionUF(int n) { parent = new int[n]; size = n; for (int i = 0; i < n; i++) { parent[i] = i; } } @Override public int size() { return size; } @Override public int find(int p) { validate(p, parent.length); while (p != parent[p]) { p = parent[p]; } return p; } @Override public boolean connected(int p, int q) { return find(p) == find(q); } @Override public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) { return; } parent[rootP] = rootQ; size--; } }
2.7.4 WeightedQuickUnionUF
加权 quick-union算法,是目前所有实现中最优的算法
package ds.impl; import ds.UF; public class WeightedQuickUnionUF implements UF { private final int[] parent; private final int[] num; private int size; public WeightedQuickUnionUF(int n) { size = n; parent = new int[n]; num = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; num[i] = 1; } } @Override public int size() { return size; } @Override public int find(int p) { validate(p, parent.length); while (p != parent[p]) { p = parent[p]; } return p; } @Override public boolean connected(int p, int q) { return find(p) == find(q); } @Override public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) { return; } // make smaller root point to larger one if (num[rootP] < num[rootQ]) { parent[rootP] = rootQ; num[rootQ] += num[rootP]; } else { parent[rootQ] = rootP; num[rootP] += num[rootQ]; } size--; } }
2.8 测试
2.8.1 测试Stack
Dijkstra的双栈算数表达式求值算法
package test; import java.util.Scanner; import ds.impl.LinkedStack; public class StackTest { public static void main(String[] args) { evaluate(); } /** * Dijkstra的双栈算数表达式求值算法 */ public static void evaluate() { String str = "( 1 + ( ( 2.3 + 3 ) / ( sqrt ( 16 ) * ( 5 % 9 ) ) ) )"; LinkedStack<String> opStack = new LinkedStack<>(); LinkedStack<Double> valStack = new LinkedStack<>(); Scanner scanner = new Scanner(str); while (scanner.hasNext()) { String s = scanner.next(); System.out.print(s + ' '); switch (s) { case "+": case "-": case "*": case "/": case "%": case "sqrt": opStack.push(s); break; case "(": break; case ")": String op = opStack.pop(); double v = valStack.pop(); switch (op) { case "+": v = valStack.pop() + v; break; case "-": v = valStack.pop() - v; break; case "*": v = valStack.pop() * v; break; case "/": v = valStack.pop() / v; break; case "%": v = valStack.pop() % v; break; case "sqrt": v = Math.sqrt(v); break; default: break; } valStack.push(v); break; default: valStack.push(Double.parseDouble(s)); break; } } System.out.printf("= %f\n", valStack.pop()); } }
2.8.2 测试Union-Find
package test; import ds.UF; import ds.impl.DefaultUF; import ds.impl.QuickFindUF; import ds.impl.QuickUnionUF; public class UFTest { public static void main(String[] args) { UF uf; int findResult; uf = new QuickFindUF(10); uf.union(4, 3); uf.union(3, 8); uf.union(6, 5); uf.union(9, 4); uf.union(2, 1); uf.union(5, 0); uf.union(7, 2); uf.union(6, 1); findResult = uf.find(3); System.out.println(findResult); System.out.println(uf.size()); System.out.println(uf.connected(4, 3)); System.out.println(uf.connected(9, 3)); uf = new DefaultUF(10); uf.union(4, 3); uf.union(3, 8); uf.union(6, 5); uf.union(9, 4); uf.union(2, 1); uf.union(5, 0); uf.union(7, 2); uf.union(6, 1); findResult = uf.find(3); System.out.println(findResult); System.out.println(uf.size()); System.out.println(uf.connected(4, 3)); System.out.println(uf.connected(9, 3)); uf = new QuickUnionUF(10); uf.union(4, 3); uf.union(3, 8); uf.union(6, 5); uf.union(9, 4); uf.union(2, 1); uf.union(5, 0); uf.union(7, 2); uf.union(6, 1); findResult = uf.find(3); System.out.println(findResult); System.out.println(uf.size()); System.out.println(uf.connected(4, 3)); System.out.println(uf.connected(9, 3)); } }
3 排序算法
3.1 定义排序工具的类结构
需要实现排序器,以及通过静态方法调用。
package util; import java.util.Arrays; public class Sort { public static void main(String[] args) { String[] a = { "1", "2", "3", "a", "a1", "b2", "a0", "_" }; //Sort.heapSort(a); //Sort.quickSort3way(a, 0, a.length - 1); System.out.println(Arrays.toString(a)); } /** * 根据数组的两个下标交换数组中的元素 * * @param <T> * @param array * @param i * @param j */ private static <T extends Comparable> void swap(T[] array, int i, int j) { T tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 判断a是否小于b * * @param <T> * @param a * @param b * @return */ private static <T extends Comparable> boolean less(T a, T b) { return a.compareTo(b) < 0; } /** * 判断a是否等于b * * @param <T> * @param a * @param b * @return */ private static <T extends Comparable> boolean eq(T a, T b) { return a.compareTo(b) == 0; } /** * 判断数组是否排序 * * @param <T> * @param array * @return */ public static <T extends Comparable> boolean isSorted(T[] array) { for (int i = 1; i < array.length; i++) { if (less(array[i], array[i - 1])) { return false; } } return true; } /** * 打印数组 * * @param <T> * @param array */ public static <T extends Comparable> void print(T[] array) { for (T t : array) { System.out.print(t + " "); } System.out.println(); } }
3.2 选择排序
时间复杂度O(n^2),辅助空间O(1),不稳定
public static <T extends Comparable> void selectSort(T[] a) { int len = a.length; for (int i = 0; i < len; i++) { int min = i; for (int j = i + 1; j < len; j++) { if (less(a[j], a[min])) { min = j; } } swap(a, i, min); } }
3.3 插入排序
时间复杂度O(n^2),辅助空间O(1),稳定
public static <T extends Comparable> void insertSort(T[] a) { insertSort(a, 0, a.length); } public static <T extends Comparable> void insertSort(T[] a, int low, int high) { for (int i = low + 1; i < high; i++) { for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { swap(a, j, j - 1); } } }
3.4 希尔排序
时间复杂度O(n^1.25),辅助空间O(1),不稳定
public static <T extends Comparable> void shellSort(T[] a) { int len = a.length; int h = 1; while (h < len / 3) { h = 3 * h + 1; } for (; h >= 1; h /= 3) { for (int i = h; i < len; i++) { for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) { swap(a, j, j - h); } } } }
3.5 归并排序
时间复杂度O(nlog(n)),辅助空间O(nlog(n)),稳定
3.5.1 归并排序的合并方法
/** * 归并排序所需的辅助数组。不将其声明为方法内的局部变量,是为了避免重复创建数组 */ private static Comparable[] mergeAux; /** * 归并排序的合并方法 * <pre> * 该方法先将所有元素复制到辅助数组中,再归并回数组a中。 * 在归并时进行了4个条件判断: * - 左半边用尽(取右半边的元素) * - 右半边用尽(取左半边的元素) * - 右半边当前元素小于左半边的当前元素(取右半边的元素) * - 右半边当前元素大于等于左半边的当前元素(取左半边元素) * </pre> * * @param <T> * @param a * @param low * @param middle * @param high */ private static <T extends Comparable> void merge(T[] a, int low, int middle, int high) { int i = low; int j = middle + 1; for (int k = low; k <= high; k++) { mergeAux[k] = a[k]; } for (int k = low; k <= high; k++) { if (i > middle) { a[k] = (T) mergeAux[j++]; } else if (j > high) { a[k] = (T) mergeAux[i++]; } else if (less(mergeAux[j], mergeAux[i])) { a[k] = (T) mergeAux[j++]; } else { a[k] = (T) mergeAux[i++]; } } }
3.5.2 自顶向下的归并排序
public static <T extends Comparable> void mergeSort(T[] a) { mergeAux = new Comparable[a.length]; mergeSort(a, 0, a.length - 1); } public static <T extends Comparable> void mergeSort(T[] a, int low, int high) { if (high <= low) { return; } int middle = low + (high - low) / 2; mergeSort(a, low, middle); mergeSort(a, middle + 1, high); merge(a, low, middle, high); }
3.5.3 自底向上的归并排序
自底向上的归并排序适用于链表组织的数据
public static <T extends Comparable> void mergeSort2(T[] a) { int N = a.length; mergeAux = new Comparable[a.length]; for (int i = 1; i < N; i = i + i) { for (int low = 0; low < N - i; low += i + i) { merge(a, low, low + i - 1, Math.min(low + i + i - 1, N - 1)); } } }
3.6 快速排序
时间复杂度O(nlog(n)),辅助空间O(nlog(n)),不稳定。非特殊场景下,最快的排序算法
3.6.1 常规快速排序
/** * 常规快速排序的划分方法 * * @param <T> * @param a * @param low * @param high * @return */ private static <T extends Comparable> int partition(T[] a, int low, int high) { int i = low; int j = high; T p = a[low]; while (i < j) { while (i < j && (less(p, a[j]) || eq(a[j], p))) { j--; } if (i < j) { swap(a, i++, j); } while (i < j && (less(a[i], p) || eq(a[i], p))) { i++; } if (i < j) { swap(a, i, j--); } } return j; } /** * 常规快速排序的排序方法 * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSort(T[] a, int low, int high) { int p; if (low < high) { p = partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p + 1, high); } }
3.6.2 排序前先洗牌
/** * 快速排序:在排序前先洗牌(可以参考随机化算法-舍伍德算法) * <pre> * 快速排序的算法改进: * 【切换到插入排序】【三取样切分】【熵最优的排序,三向切分】 * <pre> * 三取样切分 * (1)使用子数组的一小部分元素的中位数来切分数组,这样能切分得更好,但是需要计算中位数 * (2)人们发现将大小设为3并用大小居中的元素切分得效果最好 * </pre> * </pre> * * * @param <T> * @param a */ public static <T extends Comparable> void quickSort(T[] a) { Shuffle.shuffle(a); quickSort(a, 0, a.length - 1); // quickSortInsert(a, 0, a.length - 1); // quickSort3way(a, 0, a.length - 1); }
以下是该洗牌算法的实现
package util; import java.util.Arrays; /** * 设计一种公平的洗牌算法(算法导论) * * @author zhaoxuyang */ public class Shuffle { public static void main(String[] args) { Integer[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }; shuffle(a); System.out.println(Arrays.toString(a)); } public static <T extends Comparable> void shuffle(T[] arr) { for (int i = arr.length - 1; i >= 0; i--) { swap(arr, i, rand(0, i)); } } private static int rand(int begin, int end) { return (int) (begin + Math.random() * (end - begin + 1)); } private static <T extends Comparable> void swap(T[] arr, int i, int j) { T t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
3.6.3 快速排序的改进方法-小数据量转成插入排序
/** * 快速排序的改进方法-小数据量转成插入排序 * <pre> * (1)对于小数组,快速排序比插入排序慢; * (2)因为递归,快速排序的sort方***调用自己。 * </pre> * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSortInsert(T[] a, int low, int high) { int m = 65535; if (high <= low + m) { insertSort(a, low, high); return; } int lt = low; int i = low + 1; int gt = high; T v = a[low]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) { swap(a, lt++, i++); } else if (cmp > 0) { swap(a, i, gt--); } else { i++; } } quickSort(a, low, lt - 1); quickSort(a, gt + 1, high); }
3.6.4 快速排序的改进方法-三向切分
/** * 快速排序的改进方法-三向切分(可以参考荷兰国旗问题) * <pre> * 对于存在大量重复元素的数组,三向切分比常规快排高效得多。 * </pre> * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSort3way(T[] a, int low, int high) { if (high <= low) { return; } int lt = low; int i = low + 1; int gt = high; T v = a[low]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) { swap(a, lt++, i++); } else if (cmp > 0) { swap(a, i, gt--); } else { i++; } } quickSort(a, low, lt - 1); quickSort(a, gt + 1, high); }
3.7 堆排序
时间复杂度O(nlog(n)),辅助空间O(nlog(n)),不稳定
public static <T extends Comparable> void heapSort(T[] a) { int n = a.length; for (int k = n / 2; k >= 1; k--) { sink(a, k, n); } while (n > 1) { swap(a, 1 - 1, (n--) - 1); sink(a, 1, n); } } private static <T extends Comparable> void sink(T[] pq, int k, int n) { while (2 * k <= n) { int j = 2 * k; if (j < n && less(pq[j - 1], pq[j])) { j++; } if (!less(pq[k - 1], pq[j - 1])) { break; } swap(pq, k - 1, j - 1); k = j; } }
3.8 最终的排序工具
package util; import java.util.Arrays; /** * 排序 * * @author zhaoxuyang */ public class Sort { public static void main(String[] args) { String[] a = { "1", "2", "3", "a", "a1", "b2", "a0", "_" }; //Sort.heapSort(a); //Sort.quickSort3way(a, 0, a.length - 1); System.out.println(Arrays.toString(a)); } /** * 堆排序 * * @param <T> * @param a */ public static <T extends Comparable> void heapSort(T[] a) { int n = a.length; for (int k = n / 2; k >= 1; k--) { sink(a, k, n); } while (n > 1) { swap(a, 1 - 1, (n--) - 1); sink(a, 1, n); } } private static <T extends Comparable> void sink(T[] pq, int k, int n) { while (2 * k <= n) { int j = 2 * k; if (j < n && less(pq[j - 1], pq[j])) { j++; } if (!less(pq[k - 1], pq[j - 1])) { break; } swap(pq, k - 1, j - 1); k = j; } } /** * 快速排序:在排序前先洗牌(可以参考随机化算法-舍伍德算法) * <pre> * 快速排序的算法改进: * 【切换到插入排序】【三取样切分】【熵最优的排序,三向切分】 * <pre> * 三取样切分 * (1)使用子数组的一小部分元素的中位数来切分数组,这样能切分得更好,但是需要计算中位数 * (2)人们发现将大小设为3并用大小居中的元素切分得效果最好 * </pre> * </pre> * * * @param <T> * @param a */ public static <T extends Comparable> void quickSort(T[] a) { Shuffle.shuffle(a); quickSort(a, 0, a.length - 1); // quickSortInsert(a, 0, a.length - 1); // quickSort3way(a, 0, a.length - 1); } /** * 快速排序的改进方法-小数据量转成插入排序 * <pre> * (1)对于小数组,快速排序比插入排序慢; * (2)因为递归,快速排序的sort方***调用自己。 * </pre> * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSortInsert(T[] a, int low, int high) { int m = 65535; if (high <= low + m) { insertSort(a, low, high); return; } int lt = low; int i = low + 1; int gt = high; T v = a[low]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) { swap(a, lt++, i++); } else if (cmp > 0) { swap(a, i, gt--); } else { i++; } } quickSort(a, low, lt - 1); quickSort(a, gt + 1, high); } /** * 快速排序的改进方法-三向切分(可以参考荷兰国旗问题) * <pre> * 对于存在大量重复元素的数组,三向切分比常规快排高效得多。 * </pre> * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSort3way(T[] a, int low, int high) { if (high <= low) { return; } int lt = low; int i = low + 1; int gt = high; T v = a[low]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) { swap(a, lt++, i++); } else if (cmp > 0) { swap(a, i, gt--); } else { i++; } } quickSort(a, low, lt - 1); quickSort(a, gt + 1, high); } /** * 常规快速排序的排序方法 * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void quickSort(T[] a, int low, int high) { int p; if (low < high) { p = partition(a, low, high); quickSort(a, low, p - 1); quickSort(a, p + 1, high); } } /** * 常规快速排序的划分方法 * * @param <T> * @param a * @param low * @param high * @return */ private static <T extends Comparable> int partition(T[] a, int low, int high) { int i = low; int j = high; T p = a[low]; while (i < j) { while (i < j && (less(p, a[j]) || eq(a[j], p))) { j--; } if (i < j) { swap(a, i++, j); } while (i < j && (less(a[i], p) || eq(a[i], p))) { i++; } if (i < j) { swap(a, i, j--); } } return j; } /** * 归并排序所需的辅助数组。不将其声明为方法内的局部变量,是为了避免重复创建数组 */ private static Comparable[] mergeAux; /** * 自底向上的归并排序(适用于链表组织的数据) * * @param <T> * @param a */ public static <T extends Comparable> void mergeSort2(T[] a) { int N = a.length; mergeAux = new Comparable[a.length]; for (int i = 1; i < N; i = i + i) { for (int low = 0; low < N - i; low += i + i) { merge(a, low, low + i - 1, Math.min(low + i + i - 1, N - 1)); } } } /** * 自顶向下的归并排序 * * @param <T> * @param a */ public static <T extends Comparable> void mergeSort(T[] a) { mergeAux = new Comparable[a.length]; mergeSort(a, 0, a.length - 1); } /** * 自顶向下的归并排序 * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void mergeSort(T[] a, int low, int high) { if (high <= low) { return; } int middle = low + (high - low) / 2; mergeSort(a, low, middle); mergeSort(a, middle + 1, high); merge(a, low, middle, high); } /** * 归并排序的合并方法 * <pre> * 该方法先将所有元素复制到辅助数组中,再归并回数组a中。 * 在归并时进行了4个条件判断: * - 左半边用尽(取右半边的元素) * - 右半边用尽(取左半边的元素) * - 右半边当前元素小于左半边的当前元素(取右半边的元素) * - 右半边当前元素大于等于左半边的当前元素(取左半边元素) * </pre> * * @param <T> * @param a * @param low * @param middle * @param high */ private static <T extends Comparable> void merge(T[] a, int low, int middle, int high) { int i = low; int j = middle + 1; for (int k = low; k <= high; k++) { mergeAux[k] = a[k]; } for (int k = low; k <= high; k++) { if (i > middle) { a[k] = (T) mergeAux[j++]; } else if (j > high) { a[k] = (T) mergeAux[i++]; } else if (less(mergeAux[j], mergeAux[i])) { a[k] = (T) mergeAux[j++]; } else { a[k] = (T) mergeAux[i++]; } } } /** * 希尔排序 * * @param <T> * @param a */ public static <T extends Comparable> void shellSort(T[] a) { int len = a.length; int h = 1; while (h < len / 3) { h = 3 * h + 1; } for (; h >= 1; h /= 3) { for (int i = h; i < len; i++) { for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) { swap(a, j, j - h); } } } } /** * 插入排序 * * @param <T> * @param a */ public static <T extends Comparable> void insertSort(T[] a) { insertSort(a, 0, a.length); } /** * 插入排序 * * @param <T> * @param a * @param low * @param high */ public static <T extends Comparable> void insertSort(T[] a, int low, int high) { for (int i = low + 1; i < high; i++) { for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { swap(a, j, j - 1); } } } /** * 选择排序 * * @param <T> * @param a */ public static <T extends Comparable> void selectSort(T[] a) { int len = a.length; for (int i = 0; i < len; i++) { int min = i; for (int j = i + 1; j < len; j++) { if (less(a[j], a[min])) { min = j; } } swap(a, i, min); } } /** * 根据数组的两个下标交换数组中的元素 * * @param <T> * @param array * @param i * @param j */ private static <T extends Comparable> void swap(T[] array, int i, int j) { T tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 判断a是否小于b * * @param <T> * @param a * @param b * @return */ private static <T extends Comparable> boolean less(T a, T b) { return a.compareTo(b) < 0; } /** * 判断a是否等于b * * @param <T> * @param a * @param b * @return */ private static <T extends Comparable> boolean eq(T a, T b) { return a.compareTo(b) == 0; } /** * 判断数组是否排序 * * @param <T> * @param array * @return */ public static <T extends Comparable> boolean isSorted(T[] array) { for (int i = 1; i < array.length; i++) { if (less(array[i], array[i - 1])) { return false; } } return true; } /** * 打印数组 * * @param <T> * @param array */ public static <T extends Comparable> void print(T[] array) { for (T t : array) { System.out.print(t + " "); } System.out.println(); } }
洗牌算法(Shuffle)
package util; import java.util.Arrays; /** * 设计一种公平的洗牌算法(算法导论) * * @author zhaoxuyang */ public class Shuffle { public static void main(String[] args) { Integer[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }; shuffle(a); System.out.println(Arrays.toString(a)); } public static <T extends Comparable> void shuffle(T[] arr) { for (int i = arr.length - 1; i >= 0; i--) { swap(arr, i, rand(0, i)); } } private static int rand(int begin, int end) { return (int) (begin + Math.random() * (end - begin + 1)); } private static <T extends Comparable> void swap(T[] arr, int i, int j) { T t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }
4 搜索
4.1 二分搜索(binarySearch)
public static int binarySearch(int[] a, int key) { int low = 0; int high = a.length - 1; while (low <= high) { int middle = low + (high - low) / 2; if (key < a[middle]) { high = middle - 1; } else if (key > a[middle]) { low = middle + 1; } else { return middle; } } return -1; }
4.2 优先队列(MaxPriorityQueue)
package ds.impl; import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; public class MaxPriorityQueue<T> implements Iterable<T> { private T[] pq; private int size; private Comparator<T> comparator; public MaxPriorityQueue(int capacity, Comparator comparator) { pq = (T[]) new Object[capacity + 1]; size = 0; this.comparator = comparator; } public MaxPriorityQueue(int capacity) { this(capacity, null); } public MaxPriorityQueue(Comparator comparator) { this(1, comparator); } public MaxPriorityQueue() { this(1); } public MaxPriorityQueue(T[] keys) { size = keys.length; pq = (T[]) new Object[size + 1]; System.arraycopy(keys, 0, pq, 1, size); for (int k = size / 2; k >= 1; k--) { sink(k); } } public void insert(T key) { if (size == pq.length - 1) { resize(2 * pq.length); } pq[++size] = key; swim(size); } public T max() { notEmptyCheck(); return pq[1]; } public T deleteMax() { notEmptyCheck(); T result = pq[1]; swap(1, size--); sink(1); pq[size + 1] = null; if ((size > 0) && (size == (pq.length - 1) / 4)) { resize(pq.length / 2); } return result; } private void notEmptyCheck() { if (isEmpty()) { throw new NoSuchElementException(); } } @Override public Iterator<T> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<T> { private MaxPriorityQueue<T> copy; public HeapIterator() { if (comparator == null) { copy = new MaxPriorityQueue<>(size()); } else { copy = new MaxPriorityQueue<>(size(), comparator); } for (int i = 1; i <= size; i++) { copy.insert(pq[i]); } } @Override public boolean hasNext() { return !copy.isEmpty(); } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return copy.deleteMax(); } } private void sink(int k) { while (2 * k <= size) { int j = 2 * k; if (j < size && less(j, j + 1)) { j++; } if (!less(k, j)) { break; } swap(k, j); k = j; } } private boolean less(int a, int b) { if (comparator == null) { return ((Comparable<T>) pq[a]).compareTo(pq[b]) < 0; } else { return comparator.compare(pq[a], pq[b]) < 0; } } private void swap(int a, int b) { T tmp = pq[a]; pq[a] = pq[b]; pq[b] = tmp; } private void resize(int capacity) { T[] tmp = (T[]) new Object[capacity]; for (int i = 1; i <= size; i++) { tmp[i] = pq[i]; } pq = tmp; } private void swim(int k) { while (k > 1 && less(k / 2, k)) { swap(k, k / 2); k = k / 2; } } private boolean isEmpty() { return size() == 0; } private int size() { return size; } }
4.3 二叉查找树(BST)
package ds.impl; import ds.Queue; public class BST<K extends Comparable<K>, V> { private Node root; private class Node { private K key; private V value; private Node left, right; private int size; public Node(K key, V value, int size) { this.key = key; this.value = value; this.size = size; } } public int size() { return size(root); } private int size(Node x) { return x == null ? 0 : x.size; } public V get(K key) { return get(root, key); } private V get(Node x, K 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.value; } } public void put(K key, V value) { root = put(root, key, value); } private Node put(Node x, K key, V value) { if (x == null) { return new Node(key, value, 1); } int cmp = key.compareTo(x.key); if (cmp < 0) { x.left = put(x.left, key, value); } else if (cmp > 0) { x.right = put(x.right, key, value); } else { x.value = value; } x.size = size(x.left) + size(x.right) + 1; return x; } public K minKey() { return minKey(root).key; } private Node minKey(Node x) { return x.left == null ? x : minKey(x.left); } public K maxKey() { return maxKey(root).key; } private Node maxKey(Node x) { return x.right == null ? x : maxKey(x.right); } public K floorKey(K key) { Node x = floorKey(root, key); return x == null ? null : x.key; } private Node floorKey(Node x, K key) { if (x == null) { return null; } int cmp = key.compareTo(x.key); if (cmp == 0) { return x; } if (cmp < 0) { return floorKey(x, key); } Node t = floorKey(x.right, key); return t != null ? t : x; } public K ceilKey(K key) { Node x = ceilKey(root, key); return x == null ? null : x.key; } private Node ceilKey(Node x, K key) { if (x == null) { return null; } int cmp = key.compareTo(x.key); if (cmp == 0) { return x; } if (cmp > 0) { return ceilKey(x, key); } Node t = ceilKey(x.left, key); return t != null ? t : x; } public K selectKey(int k) { return selectKey(root, k).key; } private Node selectKey(Node x, int k) { if (x == null) { return null; } int t = size(x.left); if (t > k) { return selectKey(x.left, k); } else if (t < k) { return selectKey(x.right, k - t - 1); } else { return x; } } public int rankKey(K key) { return rankKey(root, key); } private int rankKey(Node x, K key) { if (x == null) { return 0; } int cmp = key.compareTo(x.key); if (cmp < 0) { return rankKey(x.left, key); } else if (cmp > 0) { return 1 + size(x.left) + rankKey(x.right, key); } else { return size(x.left); } } 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(K key) { root = delete(root, key); } private Node delete(Node x, K 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 = minKey(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.size = size(x.left) + size(x.right) + 1; return x; } public Iterable<K> keys() { return keys(minKey(), maxKey()); } private Iterable<K> keys(K lowKey, K highKey) { LinkedQueue<K> queue = new LinkedQueue<>(); keys(root, queue, lowKey, highKey); return queue; } private void keys(Node x, Queue<K> queue, K lowKey, K highKey) { if (x == null) { return; } int cmpLow = lowKey.compareTo(x.key); int cmpHigh = highKey.compareTo(x.key); if (cmpLow < 0) { keys(x.left, queue, lowKey, highKey); } if (cmpLow <= 0 && cmpHigh >= 0) { queue.enqueue(x.key); } if (cmpHigh > 0) { keys(x.right, queue, lowKey, highKey); } } }
4.4 红黑二叉查找树(RedBlackBST)
package ds.impl; import java.util.NoSuchElementException; public class RedBlackBST<K extends Comparable<K>, V> { private Node root; private class Node { private K key; private V value; private Node left; private Node right; private boolean isRed; private int size; public Node(K key, V value, boolean isRed, int size) { this.isRed = isRed; this.key = key; this.value = value; this.size = size; } } private boolean isRed(Node x) { return x == null ? false : x.isRed; } private int size(Node x) { return x == null ? 0 : x.size; } public int size() { return size(root); } public boolean isEmpty() { return root == null; } public V get(K key) { if (key == null) { throw new IllegalArgumentException(); } return get(root, key); } private V get(Node x, K 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.value; } // while (x != null) { // int cmp = key.compareTo(x.key); // if (cmp < 0) { // x = x.left; // } else if (cmp > 0) { // x = x.right; // } else { // return x.value; // } // } // return null; } public boolean containsKey(K key) { return get(key) != null; } private void delete(K key) { if (key == null) { throw new IllegalArgumentException(); } if (!containsKey(key)) { return; } if (!isRed(root.left) && !isRed(root.right)) { root.isRed = true; } root = delete(root, key); if (!isEmpty()) { root.isRed = false; } } private Node delete(Node x, K key) { int cmp = key.compareTo(x.key); if (cmp < 0) { if (!isRed(x.left) && !isRed(x.left.left)) { x = moveRedLeft(x); } x.left = delete(x.left, key); } else { if (isRed(x.left)) { x = rotateRight(x); } if (key.compareTo(x.key) == 0 && x.right == null) { return null; } if (!isRed(x.right) && !isRed(x.right.left)) { x = moveRedRight(x); } if (key.compareTo(x.key) == 0) { Node rightMinNode = min(); x.key = rightMinNode.key; x.value = rightMinNode.value; x.right = deleteMin(x.right); } else { x.right = delete(x.right, key); } } return balance(x); } public void put(K key, V value) { if (key == null) { throw new IllegalArgumentException(); } if (value == null) { delete(key); return; } root = put(root, key, value); root.isRed = false; } private Node put(Node x, K key, V value) { if (x == null) { return new Node(key, value, true, 1); } int cmp = key.compareTo(x.key); if (cmp < 0) { x.left = put(x.left, key, value); } else if (cmp > 0) { x.right = put(x.right, key, value); } else { x.value = value; } if (isRed(x.right) && !isRed(x.left)) { x = rotateLeft(x); } else if (isRed(x.left) && !isRed(x.right)) { x = rotateRight(x); } else if (isRed(x.left) && isRed(x.right)) { flipColors(x); } x.size = size(x.left) + size(x.right) + 1; return x; } private Node rotateLeft(Node x) { Node result = x.right; x.right = result.left; result.left = x; result.isRed = result.left.isRed; result.left.isRed = true; result.size = x.size; x.size = size(x.left) + size(x.right) + 1; return result; } private Node rotateRight(Node x) { Node result = x.left; x.left = result.right; result.right = x; result.isRed = result.right.isRed; result.right.isRed = true; result.size = x.size; x.size = size(x.left) + size(x.right) + 1; return result; } private void flipColors(Node x) { x.isRed = !x.isRed; x.left.isRed = !x.left.isRed; x.right.isRed = !x.right.isRed; } private Node moveRedLeft(Node x) { flipColors(x); if (isRed(x.right.left)) { x.right = rotateRight(x.right); x = rotateLeft(x); flipColors(x); } return x; } private Node moveRedRight(Node x) { flipColors(x); if (isRed(x.left.left)) { x = rotateRight(x); flipColors(x); } return x; } private Node min() { throw new UnsupportedOperationException(); } private Node deleteMin(Node right) { throw new UnsupportedOperationException(); } private Node balance(Node x) { if (isRed(x.right)) { x = rotateLeft(x); } if (isRed(x.left) && isRed(x.left.left)) { x = rotateRight(x); } if (isRed(x.left) && isRed(x.right)) { flipColors(x); } x.size = size(x.left) + size(x.right) + 1; return x; } public int height() { return height(root); } private int height(Node x) { if (x == null) { return -1; } return 1 + mathMax(height(x.left), height(x.right)); } private int mathMax(int a, int b) { return a > b ? a : b; } public K minKey() { if (isEmpty()) { throw new NoSuchElementException(); } return minKey(root).key; } private Node minKey(Node x) { return x.left == null ? x : minKey(x.left); } public K maxKey() { if (isEmpty()) { throw new NoSuchElementException(); } return maxKey(root).key; } private Node maxKey(Node x) { return x.right == null ? x : maxKey(x.right); } public Iterable<K> keys() { if (isEmpty()) { return new LinkedQueue<K>(); } return keys(minKey(), maxKey()); } public Iterable<K> keys(K lo, K hi) { if (lo == null) { throw new IllegalArgumentException("first argument to keys() is null"); } if (hi == null) { throw new IllegalArgumentException("second argument to keys() is null"); } LinkedQueue<K> queue = new LinkedQueue<>(); // if (isEmpty() || lo.compareTo(hi) > 0) return queue; keys(root, queue, lo, hi); return queue; } private void keys(Node x, LinkedQueue<K> queue, K lo, K 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); } } public static void main(String[] args) { RedBlackBST<String, Integer> st = new RedBlackBST<>(); for (int i = 0; i < 100000; i++) { String key = "key" + i; Integer value = (int) (Math.random() * 10000); st.put(key, value); } for (String s : st.keys()) { System.out.println(s + " " + st.get(s)); } System.out.println(); } }
4.5 B-树(BTree)
package ds.impl; import ds.Container; public class BTree<K extends Comparable<K>, V> implements Container { private static final int M = 4; private Node root; private int height; private int size; private static class Node { private int m; private final Entry[] children = new Entry[M]; public Node(int k) { m = k; } } private static class Entry { private Comparable key; private final Object value; private Node next; public Entry(Comparable key, Object value, Node next) { this.key = key; this.value = value; this.next = next; } } public BTree() { root = new Node(0); } @Override public int size() { return size; } public int height() { return height; } public V get(K key) { if (key == null) { throw new IllegalArgumentException(); } return search(root, key, height); } private V search(Node node, K key, int height) { Entry[] children = node.children; if (height == 0) { for (int i = 0; i < node.m; i++) { if (eq(key, children[i].key)) { return (V) children[i].value; } } } else { for (int i = 0; i < node.m; i++) { if (i + 1 == node.m || less(key, children[i + 1].key)) { return search(children[i].next, key, height - 1); } } } return null; } private boolean eq(Comparable k1, Comparable k2) { return k1.compareTo(k2) == 0; } private boolean less(Comparable k1, Comparable k2) { return k1.compareTo(k2) < 0; } public void put(K key, V value) { if (key == null) { throw new IllegalArgumentException(); } Node u = insert(root, key, value, this.height); size++; if (u == null) { return; } Node t = new Node(2); t.children[0] = new Entry(root.children[0].key, null, root); t.children[1] = new Entry(u.children[0].key, null, u); root = t; height++; } private Node insert(Node node, K key, V value, int height) { int i; Entry entry = new Entry(key, value, null); if (height == 0) { for (i = 0; i < node.m; i++) { if (less(key, node.children[i].key)) { break; } } } else { for (i = 0; i < node.m; i++) { if ((i + 1 == node.m) || less(key, node.children[i + 1].key)) { Node next = node.children[i++].next; Node u = insert(next, key, value, height - 1); if (u == null) { return null; } entry.key = u.children[0].key; entry.next = u; break; } } } for (int j = node.m; j > i; j--) { node.children[j] = node.children[j - 1]; } node.children[i] = entry; node.m++; if (node.m < M) { return null; } else { return split(node); } } private Node split(Node node) { int m = M / 2; Node result = new Node(m); node.m = m; for (int j = 0; j < m; j++) { result.children[j] = node.children[m + j]; } return result; } @Override public String toString() { return toString(root, height, "") + "\n"; } private String toString(Node node, int height, String indent) { StringBuilder s = new StringBuilder(); Entry[] children = node.children; if (height == 0) { for (int j = 0; j < node.m; j++) { s.append(indent) .append(children[j].key) .append('=') .append(children[j].value) .append('\n'); } } else { for (int j = 0; j < node.m; j++) { if (j > 0) { s.append(indent) .append('(') .append(children[j].key) .append(')') .append('\n'); } s.append(toString(children[j].next, height - 1, indent + "#")); } } return s.toString(); } public static void main(String[] args) { BTree<String, String> st = new BTree<>(); st.put("www.cs.princeton.edu", "128.112.136.12"); st.put("www.cs.princeton.edu", "128.112.136.11"); st.put("www.princeton.edu", "128.112.128.15"); st.put("www.yale.edu", "130.132.143.21"); st.put("www.simpsons.com", "209.052.165.60"); st.put("www.apple.com", "17.112.152.32"); st.put("www.amazon.com", "207.171.182.16"); st.put("www.ebay.com", "66.135.192.87"); st.put("www.cnn.com", "64.236.16.20"); st.put("www.google.com", "216.239.41.99"); st.put("www.nytimes.com", "199.239.136.200"); st.put("www.microsoft.com", "207.126.99.140"); st.put("www.dell.com", "143.166.224.230"); st.put("www.slashdot.org", "66.35.250.151"); st.put("www.espn.com", "199.181.135.201"); st.put("www.weather.com", "63.111.66.11"); st.put("www.yahoo.com", "216.109.118.65"); System.out.println("cs.princeton.edu: " + st.get("www.cs.princeton.edu")); System.out.println("hardvardsucks.com: " + st.get("www.harvardsucks.com")); System.out.println("simpsons.com: " + st.get("www.simpsons.com")); System.out.println("apple.com: " + st.get("www.apple.com")); System.out.println("ebay.com: " + st.get("www.ebay.com")); System.out.println("dell.com: " + st.get("www.dell.com")); System.out.println(); System.out.println("size: " + st.size()); System.out.println("height: " + st.height()); System.out.println(st); System.out.println(); } }
5 图
5.1 无向图(Graph)
package ds.impl; public class Graph { private static final String NEW_LINE = System.getProperty("line.separator"); private final int V; private int E; private LinkedBag<Integer>[] adj; public Graph(int V) { if (V < 0) { throw new IllegalArgumentException(); } this.V = V; this.E = 0; adj = (LinkedBag<Integer>[]) new LinkedBag[V]; for (int v = 0; v < V; v++) { adj[v] = new LinkedBag<>(); } } public Graph(Graph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < V; v++) { LinkedStack<Integer> reverse = new LinkedStack<>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } public int V() { return V; } public int E() { return E; } private void validateVertex(int v) { if (v < 0 || v >= V) { throw new IllegalArgumentException(); } } public void addEdge(int v1, int v2) { validateVertex(v1); validateVertex(v2); E++; adj[v1].add(v2); adj[v2].add(v1); } public Iterable<Integer> adj(int v) { validateVertex(v); return adj[v]; } public int degree(int v) { validateVertex(v); return adj[v].size(); } @Override public String toString() { StringBuilder s = new StringBuilder(); s.append("V=").append(V).append(", E=").append(E).append(NEW_LINE); for (int v = 0; v < V; v++) { s.append(v).append(": "); for (int w : adj[v]) { s.append(w).append(" "); } s.append(NEW_LINE); } return s.toString(); } public static void main(String[] args) { Graph g = new Graph(4); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println(g); } }
5.2 有向图(Digraph)
package ds.impl; public class Digraph { private static final String NEW_LINE = System.getProperty("line.separator"); private final int V; private int E; private LinkedBag<Integer>[] adj; private int[] indegree; public Digraph(int V) { if (V < 0) { throw new IllegalArgumentException(); } this.V = V; this.E = 0; indegree = new int[V]; adj = (LinkedBag<Integer>[]) new LinkedBag[V]; for (int v = 0; v < V; v++) { adj[v] = new LinkedBag<>(); } } public Digraph(Digraph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < V; v++) { this.indegree[v] = G.indegree[v]; } for (int v = 0; v < G.V(); v++) { LinkedStack<Integer> reverse = new LinkedStack<>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } public int V() { return V; } public int E() { return E; } private void validateVertex(int v) { if (v < 0 || v >= V) { throw new IllegalArgumentException(); } } public void addEdge(int v1, int v2) { validateVertex(v1); validateVertex(v2); adj[v1].add(v2); indegree[v2]++; E++; } public Iterable<Integer> adj(int v) { validateVertex(v); return adj[v]; } public int outdegree(int v) { validateVertex(v); return adj[v].size(); } public int indegree(int v) { validateVertex(v); return indegree[v]; } public Digraph reverse() { Digraph result = new Digraph(V); for (int v = 0; v < V; v++) { for (int w : adj[v]) { result.addEdge(w, v); } } return result; } @Override public String toString() { StringBuilder s = new StringBuilder(); s.append("V=").append(V).append(", E=").append(E).append(NEW_LINE); for (int v = 0; v < V; v++) { s.append(v).append(": "); for (int w : adj[v]) { s.append(w).append(" "); } s.append(NEW_LINE); } return s.toString(); } public static void main(String[] args) { Digraph g = new Digraph(4); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println(g); } }
6 贪心
6.1 Dijkstra算法-单元最短路径
6.1.1 问题描述
给定一个有向带权图
G=(V,E)
,其中每条边的权是一个非负实数。另外,给定V
中的一个顶点,称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度,这里的路径长度是指路径上经过的所有边上的权值之和。
6.1.2 贪心策略
Dijkstra算法思想: 按各个顶点与源点之间路径长度的递增次序,生成源点到各个顶点的最短路径的方法,即先求出长度最短的一条路径,再参照它求出长度次短的一条路径,依此类推,直到从源点到其它各个顶点的最短路径全部求出为止。
6.1.3 算法设计
- 源点u 。集合S中的顶点到源点的最短路径的长度已经确定,集合V-S中所包含的顶点到源点的最短路径的长度待定。
- 特殊路径:从源点出发只经过S中的点到达V-S中的点的路径。
- 贪心策略:选择特殊路径长度最短的路径,将其相连的V-S中的顶点加入到集合S中。
- 求解步骤:*
- 步骤1:设计合适的数据结构。带权邻接矩阵C,即如果< u, x >E,令
C[u][x]=<u, x >
的权值,否则,C[u][x]=无穷
;采用数组dist来记录从源点到其它顶点的最短路径长度;采用数组p来记录最短路径; - 步骤2:初始化。令集合S={u},对于集合V-S中的所有顶点x,设置
dist[x]=C[u][x]
;如果顶点i与源点相邻,设置p[i]=u
,否则p[i]=-1
; - 步骤3:在集合V-S中依照贪心策略来寻找使得dist[x]具有最小值的顶点t,t就是集合V-S中距离源点u最近的顶点。
- 步骤4:将顶点t加入集合S中,同时更新集合V-S;
- 步骤5:如果集合V-S为空,算法结束;否则,转步骤6;
- 步骤6:对集合V-S中的所有与顶点t相邻的顶点x,如果
dist[x]>dist[t]+C[t][x]
,则dist[x]=dist[t]+C[t][x]
并设置p[x]=t
。转步骤3。6.1.4 示例
public class Dijkstra { private static final int N = Integer.MAX_VALUE; private static final int[][] Graph = { {0, 1, 5, N, N, N, N, N, N}, {1, 0, 3, 7, 5, N, N, N, N}, {5, 3, 0, N, 1, 7, N, N, N}, {N, 7, N, 0, 2, N, 3, N, N}, {N, 5, 1, 2, 0, 3, 6, 9, N}, {N, N, 7, N, 3, 0, N, 5, N}, {N, N, N, 3, 6, N, 0, 2, 7}, {N, N, N, N, 9, 5, 2, 0, 4}, {N, N, N, N, N, N, 7, 4, 0}}; public static void main(String[] args) { dijkstra(0, Graph); } /** * Dijkstra最短路径。 即图中"节点vs"到其它各个节点的最短路径。 * * @param vs 起始节点 * @param Graph 图 */ public static void dijkstra(int vs, int[][] Graph) { int NUM = Graph[0].length; // 前驱节点数组 int[] prenode = new int[NUM]; // 最短距离数组 int[] mindist = new int[NUM]; // 该节点是否已经找到最短路径 boolean[] find = new boolean[NUM]; int vnear = 0; for (int i = 0; i < mindist.length; i++) { prenode[i] = i; mindist[i] = Graph[vs][i]; find[i] = false; } find[vs] = true; for (int v = 1; v < Graph.length; v++) { // 每次循环求得距离vs最近的节点vnear和最短距离min int min = N; for (int j = 0; j < Graph.length; j++) { if (!find[j] && mindist[j] < min) { min = mindist[j]; vnear = j; } } find[vnear] = true; // 根据vnear修正vs到其他所有节点的前驱节点及距离 for (int k = 0; k < Graph.length; k++) { if (!find[k] && (min + Graph[vnear][k]) < mindist[k]) { prenode[k] = vnear; mindist[k] = min + Graph[vnear][k]; } } } for (int i = 0; i < NUM; i++) { System.out.println("v" + vs + "...v" + prenode[i] + "->v" + i + ", s=" + mindist[i]); } }
}
## 7 动态规划 ### 7.1 最长公共子序列问题 ```java package net.zhaoxuyang.common.algorithm.dp; /** * 最长公共子序列 * * @author zhaoxuyang */ public class LastestCommonSequence { public static void main(String[] args) { String x = "ABCBDAB"; String y = "BDCABA"; int m = x.length(); int n = y.length(); int[][] c = new int[m + 1][n + 1]; int[][] b = new int[m + 1][n + 1]; lscLength(x.toCharArray(), y.toCharArray(), c, b); // for (int i = 0; i <= x.length(); i++) { // for (int j = 0; j <= y.length(); j++) { // System.out.print(b[i][j]+" "); // } // System.out.println(); // } lcs(x.length(), y.length(), x.toCharArray(), b); } /** * <pre> * ------------------------------------------------------------ * = 0 i=0 || j=0 * c[i][j] = c[i-1][j-1]+1 i,j>0 && x[i]=y[j] * = max(c[i][j-1],c[i-1][j]) i,j>0 && x[i]!=y[j] * * b[i][j]=1 表示c[i][j]由c[i-1][j-1]+1 得到 * b[i][j]=2 表示c[i][j]由c[i][j-1] 得到 * b[i][j]=3 表示c[i][j]由c[i-1][j] 得到 * ------------------------------------------------------------ * i行j列,初始时c[i][0]=0,c[0][j]=0 * B D C A B A * 0 0 0 0 0 0 0 * A 0 * B 0 * C 0 * B 0 * D 0 * A 0 * B 0 * ------------------------------------------------------------ * </pre> * * @param x X序列 * @param y Y序列 * @param c 存入最优值 * @param b 存入最优值的来源 */ private static void lscLength(char[] x, char[] y, int[][] c, int[][] b) { for (int i = 1; i <= x.length; i++) { for (int j = 1; j <= y.length; j++) { if (x[i - 1] == y[j - 1]) { c[i][j] = c[i - 1][j - 1] + 1; b[i][j] = 1; } else if (c[i][j - 1] > c[i - 1][j]) { c[i][j] = c[i][j - 1]; b[i][j] = 2; } else { c[i][j] = c[i - 1][j]; b[i][j] = 3; } } } } /** * 根据记录下的信息构造最优解 */ private static void lcs(int i, int j, char[] x, int[][] b) { if (i == 0 || j == 0) { return; } switch (b[i][j]) { case 1: lcs(i - 1, j - 1, x, b); visit(x[i - 1]); break; case 2: lcs(i, j - 1, x, b); break; default: lcs(i - 1, j, x, b); break; } } /** * 如何处理最优解,例如打印,或者添加到StringBuilder中 * @param c */ private static void visit(char c) { System.out.print(c); } }
7.2 0-1背包问题
package net.zhaoxuyang.common.algorithm.dp; import java.util.Arrays; /** * 0-1 背包问题 * * <pre> * n个物品和1个背包,对物品i,价值为v[i],重量为w[i],背包容量为W,如何装入使得总价值最大: * - w[i]x[i]小于等于W * - x[i]∈{0,1} * - 目标函数为max(v[i]x[i]) * - 其中i∈[1,n] * * 假如(x[1], x[2], x[3], ..., x[n])是最优解, * 那么(x[2], x[3], ..., x[n])则是以下问题的一个最优解: * - w[i]x[i] 小于等于 W - w[1]x[1] * - x[i]∈{0,1} * - 目标函数为max(v[i]x[i]) * - 其中i∈[2,n] * * </pre> * * 时间复杂度为O(nW) * 缺点:要求w数组中的元素为整数;当W>2^n时,时间复杂度为O(n2^n) * @author zhaoxuyang */ public class KnapSack { public static void main(String[] args) { int[] w = {2, 2, 6, 5, 4}; int[] v = {6, 3, 5, 4, 6}; int W = 10; byte[] result = fun(w, v, W); System.out.println(Arrays.toString(result)); } /** * * <pre> * 数组c[w.length+1][W+1]存放每次迭代的执行结果 * 数组x[w.length]存放所装入的背包的物品状态 * @初始化 c[0][j] = c[i][0] = 0 * * @递归式 c[i][j] = c[i-1][j] j 小于 w[i] * = max{c[i-1][j],c[i-1][j-w[i]]+v[i]} j大于等于w[i] * </pre> * @param w 重量 * @param v 价值 * @param W 容量 * @return 最优解 */ private static byte[] fun(int[] w, int[] v, int W) { int row = w.length; int col = W; byte[] x = new byte[row]; int[][] c = new int[row + 1][col + 1]; //存放各个子问题的最优值 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { if (j < w[i - 1]) { c[i][j] = c[i - 1][j]; } else { int tmp = c[i - 1][j - w[i - 1]] + v[i - 1]; c[i][j] = Math.max(c[i - 1][j], tmp); } } } //构造最优解 for (int i = row, j = col; i > 0; i--) { if (c[i][j] > c[i - 1][j]) { x[i - 1] = 1; j -= w[i - 1]; } } return x; } }
7.3 加工顺序问题
package net.zhaoxuyang.common.algorithm.dp; import java.util.ArrayList; import java.util.List; /** * 加工顺序 * 先a后b的加工顺序,给定a和b各工件的耗时,求加工耗时最短的序列。 * 解法: * 1. 求a中小于b的位置组g1:1,4,6;a中大于等于a的位置组g2:2,3,5,7 * 2. 对g1非减序排序,对g2非增序排序 * 3. 将g1连接上g2 * @author zhaoxuyang */ public class ProcessingSquence { public static void main(String[] args) { int[] a = {3,8,10,12,6,9,15}; int[] b = {7,2,6,18,3,10,4}; List<Integer> result = flowShop(a,b); System.out.println(result); } private static List<Integer> flowShop(int[] a, int[] b) { int len = a.length; List<Integer> g1 = new ArrayList<>(); List<Integer> g2 = new ArrayList<>(); for(int i=0;i<len;i++){ if(a[i]<b[i]){ g1.add(a[i]); }else{ g2.add(b[i]); } } g1.sort((left,right)->{ return left-right; }); g2.sort((left,right)->{ return right-left; }); g1.addAll(g2); return g1; } }
8 搜索法
8.1 图的着色问题
package net.zhaoxuyang.common.algorithm.search; /** * 图的m着色问题 * @author zhaoxuyang */ public class MColoring { public static void main(String[] args) { int n = 5; int m = 5; int[][] a = { {-1, -1, -1, -1, -1, -1}, {-1, 0, 1, 1, 1, 0}, {-1, 1, 0, 1, 1, 1}, {-1, 1, 1, 0, 1, 0}, {-1, 1, 1, 1, 0, 1}, {-1, 0, 1, 0, 1, 0} }; MColoring c = new MColoring(); long sum = c.coloring(m, n, a); System.out.println(sum); } int n; // 图的顶点数 int m; // 可用的颜色数 int[][] a;//图的邻接矩阵 int[] x;//当前解 long sum;//当前已找到的可m着色方案数 public long coloring(int m, int n, int[][] a) { this.n = n; this.a = a; x = new int[n + 1]; this.m = m; sum = 0; backtrack(1); return sum; } private void backtrack(int t) { if (t > n) { sum++; for (int i = 1; i <= n; i++) { visit(x[i]); } System.out.println(); } else { for (int i = 1; i <= m; i++) { x[t] = i; if (ok(t)) { backtrack(t + 1); } x[t] = 0; } } } private void visit(int item) { System.out.printf("%d ", item); } private boolean ok(int k) { for (int j = 1; j <= n; j++) { if (a[k][j] == 1 && x[j] == x[k]) { return false; } } return true; } }
8.2 深度优先搜索
bool Visited[n + 1]; for(int i = 1; i <= n; i++){ Visited[i] = 0; } //从顶点k出发进行深度优先搜索 void Dfsk(int k){ Visited[k] = 1; for(int j = 1; j <= n; j++){ if(c[k][j] == 1 && Visited[j] == 0){ Dfsk(j); } } } //深度优先搜索整个图 void Dfs(){ for(int i = 1; i <= n; i++){ if(Visited[i] == 0){ Dfsk(i); } } }
8.3 回溯法
8.3.1 回溯法的算法框架
为定义搜索范围,应明确以下几个方面:
- 问题解的形式:表示成一个n元组的形式
(x[0],x[1],...,x[n-1])
- 显约束:对分量
x[i]
的取值范围限定。 - 隐约束:为满足问题的解而对不同分量之间施加的约束。
- 解空间:对于问题的一个实例,解向量满足显约束的所有n元组构成了该实例的一个解空间。
在搜索的过程中,应了解几个名词:
- 扩展结点:一个正在生成孩子的结点。
- 活结点:一个自身已生成但其孩子还没有全部生成的结点。
- 死结点:一个所有孩子已生成的结点。
求解过程:
- 定义问题的解空间。
- 确定空间的组织结构。
- 搜索解空间:
- 确定约束条件
- 确定限界条件
- 搜索过程
算法描述:
(1)递归形式
// t为扩展节点在树中所处的层次 void Backtrack(int t){ if(t > n){ //搜索层次大于解空间的树的深度,说明找到了叶子结点,即找到了问题的一个解 output(x); } else { for (int i = s(n, t); i <= e(n, t); i++){ x[t] = d(i); if(constraint(t) && bound(t)){ Backtrack(t + 1); } } } }
(2)非递归形式
void NBacktrack(){ int t = 1; while(t > 0){ if(s(n,t) <= e(n, t)){ for(int i = s(n, t); i <= e(n,t); i++){ x[t] = d(i); if(constraint(t) && bound(t)){ if(t > n){ output(x); } else { t++; } } } } else { t--; } } }
8.3.2 子集树
当所给问题是从n个元素组成的集合S中找出满足某一性质的一个子集时,相应的解空间树称为子集树。
- 0-1 背包问题
- 子集和问题
- 装载问题
- 最大团问题
算法描述://x用来存放当前解,constraint()为约束函数,bound()为限界函数 void Backtrack(int t){ if(t > n){ output(x); } //判断能否沿着扩展结点的左分支进行扩展 if(constraint(t)){ //做相关标识 Backtrack(t + 1); //做相关标识的反操作 } //判断能否沿着扩展结点的右分支进行扩展 if(bount(t)){ //做相关标识 Backstrack(t + 1); //做相关标识的反操作 } }
8.3.3 排列树
当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时,相应的解空间称为排列树。
- n皇后问题
- 旅行商问题
- 批处理作业调度问题
- 圆排列问题
- 电路板排序问题
算法描述:void Backtrack(int t){ if(t > n){ output(x); } else { for(int i = t; i <= n; i++){ swap(x[t], x[i]); if(constraint(t) && bound(t)){ Backtrack(t + 1); } swap(x[t], x[i]); } } }
8.3.4 满m叉树(组合树)
当所给问题的n个元素中每一个元素均有m种选择,要求确定其中的一种选择,
使得对这n个元素的选择结果组成的向量满足某种性质,即寻找满足某种特性的n个元素取值的一个组合。
这类问题的解空间称为满m叉树。 - n皇后问题
- 图的m着色问题
- 最小机器设计问题
算法描述:void Backtrack(int t){ if(t > n) { output(x); } else { for (int i = 1; i <= m; i++) { if (constraint(t) && bound(t)) { x[t] = i; //做其他相关标识 Backtrack(t + 1); //做其他相关标识的反操作,退出相关标识 } } } }
8.4 广度优先搜索
算法描述:
bool Visited[n + 1]; for(int i = 1; i <= n; i++){ Visited[i] = 0; } void BFSVO(int v0){ int w; visit(v0); Visited[v0] = 1; InitQueue(&Q); InsertQueue(&Q, v0); while(!Empty(Q)){ DeleteQueue(&Q, &v); for(int i = 1; i <= n; i++) { if(g[v][i] != 0){ w = i; } if(!Visited(w)){ visit(w); Visited[w] = 1; InsertQueue(&Q, w); } } } } BFS(){ for(int i = 1; i <= n; i++) { if(Visited[i] = 0){ BFSVO(i); } } }
8.5 分支限界法
分支限界发先将根结点加入活结点表,接着从活结点表中取出根结点,使其成为当前扩展结点,
一次性生成所有孩子结点,判断孩子结点是舍弃还是保留,舍弃那些导致可行解或者导致非最优解的孩子结点,
其余的被保留在活结点表中。
再从活结点表中取出一个活结点,重复上述过程。
解题步骤:
- 定义问题的解空间
- 确定问题的解空间组织结构(树或图)
- 搜索解空间。搜索要定义判断标准(约束函数或限界函数),如果选用优先队列,需确定优先级。
9 随机化算法
随机化算法分类:
- 数值随机化算法:在原理上可能就不存在精确解,或者无法在可行时间内求得,因此用该算法得到相当满意的解。
- 蒙特卡罗算法:能求得问题的一个解,但这个解未必是正确的。
- 拉斯维加斯算法:绝不返回错误的解,但有时可能找不到解。
- 舍伍德算法:当一个确定性算法在最坏与平均情况时间复杂度相差较大时,引入随机性来降低最坏情况出现的概率,不会改变结果。
9.1 数值随机化算法
package net.zhaoxuyang.common.algorithm.random; /** * 数值随机化算法 * * @author zhaoxuyang */ public class Numerical { public static void main(String[] args) { System.out.println(calculatePI(1)); System.out.println(calculatePI(10)); System.out.println(calculatePI(100)); System.out.println(calculatePI(1000)); System.out.println(calculatePI(100000)); System.out.println(calculatePI(1000000)); System.out.println(calculatePI(10000000)); System.out.println(calculatePI(100000000)); System.out.println(calculateDefiniteIntegral(100000000)); } /** * 计算π的值 * @param n * @return */ static double calculatePI(int n) { double x; double y; int k = 0; for (int i = 1; i <= n; i++) { x = Math.random(); y = Math.random(); if ((x * x + y * y) <= 1) { k++; } } return 4.0 * k / n; } /** * 计算定积分(y=x^2) * @param n * @return */ static double calculateDefiniteIntegral(int n) { int k = 0; double x; double y; for (int i = 0; i <= n; i++) { x = Math.random(); y = Math.random(); double fx = 2 * x; if (y <= fx) { k++; } } return 1.0 * k / n; } }
9.2 蒙特卡罗算法
package net.zhaoxuyang.common.algorithm.random; /** * * 蒙特卡罗算法 * <pre> * 设p是一个实数,且 0.5 小于 p 小于 1, * 如果蒙特卡罗算法对于问题的任一实例得到的正确解的概率不小于p,则称该算法是正确的。 * </pre> * @author zhaoxuyang */ public class MonteCarlo { public static void main(String[] args) { //int[] array = {1, 2, 1}; // System.out.println(majority(array, array.length, 0.99)); // System.out.println(majority(array, array.length, 0.99)); System.out.println(checkPrimeByWilson(5)); System.out.println(checkPrimeByWilson(6)); while(true){ System.out.println(checkPrimeByMoteCarlo(97)); } } /** * 判断一个数组是否存在主元素 一个含有n个元素的数组,当存在一个元素占比大于n/2时,称该元素是数组的主元素。 */ static boolean majority(int[] array, double n, double p) { int k = (int) Math.ceil(Math.log(n) / Math.log(1 - 0.9)); for (int i = 1; i <= k; i++) { if (checkMajority(array, n)) { System.out.println(array[i]); return true; } } return false; } static boolean checkMajority(int[] array, double n) { int randomIndex = (int) (Math.random() * n); int item = array[randomIndex]; int k = 0; for (int i = 0; i < n; i++) { if (item == array[i]) { k++; } } return (k > 1.0 * n / 2); } /** * 常规的判断一个数是否为素数 * * @param n * @return */ boolean checkPrime(long n) { int m = (int) Math.floor(Math.sqrt(n)); for (int i = 2; i <= m; i++) { if (n % i == 0) { return false; } } return true; } /** * * <pre> * Wilson定理有很高的理论价值,定义为:对于给定的正整数n,判定n是素数的充要条件是: * (n-1)! === -1(mod n) * 例如n = 5,6,7 * (5-1)!=24, 24 mod 5 = -1(mod 5),故5是素数 * (6-1)!=120, 120 mod 6 = 0(mod 6),故6不是素数 * (7-1)!=720, 720 mod 7 = -1(mod 7),故6不是素数 * * </pre> * @param n * @return */ static boolean checkPrimeByWilson(long n) { return fan(n - 1) % n == n - 1; } static long fan(long n) { return n == 0 ? 1 : n * fan(n - 1); } static boolean checkPrimeByMoteCarlo(int n){ int m = (int) Math.floor(Math.sqrt(n)); int min = 2; int max = m - 1; int i = (int)(Math.random()*(max-min+1)+min); System.out.println(i); return n % i != 0; } }
9.3 拉斯维加斯算法
package net.zhaoxuyang.common.algorithm.random; /** * * 拉斯维加斯算法 * * <pre> * void RLV(Type x, Type &y){ * bool success = fasle; * while(!success){ * success = RLV(x, y); * } * } * </pre> * * @author zhaoxuyang */ public class LasVegas { public static void main(String[] args) { split(182); } static void pollard(int n) { int i = 1; int x = (int) (Math.random() * n +1); int y = x; int k = 2; while (true) { i++; x = (x * x - 1) % n; int d = gcd(y - x, n); if ((d > 1) && (d < n)) { System.out.print(d + " "); } if (i == k) { y = x; k *= 2; } } } /** * 整数因子分解 */ static void split(int n) { int k = (int) Math.floor(Math.sqrt(n)); for (int i = 2; i <= k; i++) { if (n % i == 0) { System.out.print(i + " "); } } } static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } }
9.4 舍伍德算法
package net.zhaoxuyang.common.algorithm.random; import java.util.Arrays; import net.zhaoxuyang.common.algorithm.other.QuickSort; import net.zhaoxuyang.common.algorithm.other.Shuffle; /** * * 舍伍德算法 * @author zhaoxuyang */ public class Sherwood { public static void main(String[] args){ int[] array = {1,2,3,4,5,6,7,8,7,6}; randomQuickSort(array); System.out.println(Arrays.toString(array)); } /** * 打乱顺序,再排序 * @param array */ static void randomQuickSort(int[] array){ Shuffle.shuffle(array); QuickSort.quickSort(array); } }
10 数论算法
10.1 Stein求最大公约数
package net.zhaoxuyang.common.algorithm.math; /** * * @author zhaoxuyang */ public class Stein { public static void main(String[] args) { System.out.println(gcd(2412122241212121212L, 2131424432543544656L)); } static long gcd(long a, long b) { if (a == 0) { return b; } if (b == 0) { return a; } if (a % 2 == 0 && b % 2 == 0) { return 2 * gcd(a >> 1, b >> 1); } else if (a % 2 == 0) { return gcd(a >> 1, b); } else if (b % 2 == 0) { return gcd(a, b >> 1); } else { return gcd(Math.abs(a - b), Math.min(a, b)); } } }
10.2 矩阵求斐波那切数列
package net.zhaoxuyang.common.algorithm.other; /** * 暴力递归,记忆搜索,矩阵求法,流处理求斐波那契数列 * 结论: * (1)流处理并没有想象中的快 * (2)暴力递归效率及其低下,N稍微大点(40左右)就已经算不出结果 * (3)矩阵求法并没有记忆搜索快,但是在计算量较大的【别的程序】中却是最快的 */ import java.util.stream.Stream; /** * * @author zhaoxuyang */ public class Fibonacci { public static void main(String[] args) throws InterruptedException { int n = 50; int res; long start; // start = System.nanoTime(); // res = f1(n); // System.out.println(res); // System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = f2(n); System.out.println(res); System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = f3(n); System.out.println(res); System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]}) .skip(n) .map(t -> t[0]) .findFirst() .get(); System.out.println(res); System.out.println(System.nanoTime() - start); /* n=20时,输出 6765 705588 6765 21391 6765 38888 6765 72026229 n=100时,注释掉O(2^N)的第一段因为要很久时间,所以后三个的输出 -980107325 166519 -980107325 43165 -980107325 72650035 */ } /** * O(2^N) * * @param n * @return */ public static int f1(int n) { if (n < 1) { return 0; } else if (n == 1 || n == 2) { return 1; } else { return f1(n - 1) + f1(n - 2); } } /** * 记忆搜索 O(N) * * @param n * @return */ public static int f2(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } int res = 1; int pre = 1; for (int i = 3; i <= n; i++) { int tmp = res; res = res + pre; pre = tmp; } return res; } /** * 矩阵求法 O(logN) * <pre> * 如果递归式严格遵循F(N)=F(N-1)+F(N-2), * 对于求第N项值,有矩阵乘法的方式可以将时间复杂度降至O(ogN) * 二阶递推数列,状态矩阵为2*2的矩阵: * * (F(n),F(n-1)) = (F(n-1),F(n-2)) * | a b | * | c d | * 斐波那契数列的前4项代入求出状态矩阵: * | a b | | 1 1 | * | c d | = | 1 0 | * * (F(n),F(n-1)) = (F(n-1), F(n-2)) * | 1 1 | = (1,1) * | 1 1 |^(n-2) * | 1 0 | | 1 0 | * 问题变成求矩阵N次方 * 以整数10的75次方为例: * 75的二进制为1001011,则10的75次方=10^64 * 10^8 * 10^2 * 10^1 * 把累乘的值相乘即可 * * 对于矩阵,求矩阵m的p次方请参看matrixPower方法,其中muliMatrix是两个矩阵相乘的具体实现 * </pre> * * @param n * @return */ public static int f3(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } int[][] base = {{1, 1}, {1, 0}}; int[][] res = matrixPower(base, n - 2); return res[0][0] + res[1][0]; } /** * @param m * @param p * @return */ private static int[][] matrixPower(int[][] m, int p) { int[][] res = new int[m.length][m[0].length]; for (int i = 0; i < res.length; i++) { res[i][i] = 1; } int[][] tmp = m; for (; p != 0; p >>= 1) { if ((p & 1) != 0) { res = muliMatrix(res, tmp); } tmp = muliMatrix(tmp, tmp); } return res; } private static int[][] muliMatrix(int[][] m1, int[][] m2) { int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m2[0].length; i++) { for (int j = 0; j < m1.length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; } }