<> One , Sorting summary

（1） Quick platoon private void quicksort(int[] array, int begin, int end) { // TODO
Auto-generated method stub if(begin<end) { int key=array[begin]; // Set the first element as the base element
int i=begin; int j=end; while(i<j) { while(i<j&&array[j]>key) { j--; } if(i<j)
{ array[i]=array[j]; i++; } while(i<j&&array[i]<key) { i++; } if(i<j) {
array[j]=array[i]; j--; } array[i]=key; // Place base element quicksort(array,begin,i-1);
quicksort(array,i+1,end); } } } （2） Heap sort public static void heapSort(int[] arr)
{ if (arr == null || arr.length < 2) { return; } for (int i = 0; i <
arr.length; i++) { heapInsert(arr, i); } int size = arr.length; swap(arr, 0,
--size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } }
// Build a heap public static void heapInsert(int[] arr, int index) { while (arr[index] >
arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1)
/ 2; } } // Stack adjustment public static void heapify(int[] arr, int index, int size) { int
left = index * 2 + 1; while (left < size) { int largest = left + 1 < size &&
arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] >
arr[index] ? largest : index; if (largest == index) { break; } swap(arr,
largest, index); index = largest; left = index * 2 + 1; } } // Exchange data public
static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j];
arr[j] = tmp; } （3） Merge sort public static void mergeSort(int[] arr) { if (arr ==
null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); }
// Specific operation of merging public static void mergeSort(int[] arr, int l, int r) { if (l == r) {
return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr,
mid + 1, r); merge(arr, l, mid, r); } // Merging process public static void merge(int[]
arr, int l, int m, int r) { int[] help = new int[r - l + 1]; int i = 0; int p1
= l; int p2 = m + 1; while (p1 <= m && p2 <= r) { help[i++] = arr[p1] < arr[p2]
? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2
<= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i]
= help[i]; } }
<> Two , Find summary

Search order : The sequence itself does not need to be ordered , Poor lookup performance , The average search length is (1+n)/2, The time complexity is O(n).
Binary search : Sequence order is required
Matrix search with increasing row and column ： According to the special storage mode of young matrix
Block search ： Improvement of sequential search and binary search
Other search algorithms :** Depth first search , Breadth first search , Binary tree search ( before , in , after , level traversal )** etc .
(1) Binary search /** * Binary search by recursion * @param key */ public int SearchRecursion(int key) {
if(array!=null) { return searchRecursion(key,0,array.length-1); } return -1; }
private int searchRecursion(int key, int start, int end) { // TODO
Auto-generated method stub if(start>end) { return -1; } int
mid=start+(end-start)/2; if(array[mid]==key) { return mid; } else
if(array[mid]<key) { return searchRecursion( key, mid+1, end); }else { return
searchRecursion( key, start, mid-1); } } /** * Non recursive implementation of binary search * @param key */
public int search(int key) { if(array==null) { return -1; } int start=0; int
end=array.length-1; while(start<=end) { int mid =start+(end-start)/2;
if(array[mid]==key) { return mid; } else if(array[mid]<key) { start=mid+1;
}else { end=mid-1; } } return -1; }
<> Three , string matching KMP
classic KMP algorithm // method : Get the position of the pattern string in the bus string public static int KMP(String s,String m){
if(s==null||m==null||m.length()<1||s.length()<m.length()){ return -1; }
char[]ss=s.toCharArray(); // Main string string to array char[]ms=m.toCharArray(); // Substring string to array int
si=0; int mi=0; int[]next=getNextArray(ms); while(si<ss.length&&mi<ms.length){
if(ss[si]==ms[mi]){ si++; mi++; }else if(next[mi]==-1){ si++; }else{
mi=next[mi]; } } return mi==ms.length?si-mi:-1; } // Of the pattern string next array public static
int[]getNextArray(char[]ms){ if(ms.length==1){ return new int[]{-1}; }
int[]next=new int[ms.length]; next[0]=-1; next[1]=0; int pos=2; int cn=0;
while(pos<ms.length){ if(ms[pos-1]==ms[cn]){ next[pos++]=++cn; }else if(cn>0){
cn=next[cn]; }else{ next[pos++]=0; } } return next; }
<> Four , Traversal of binary tree
public static class Node { public int value; public Node left; public Node
right; public Node(int data) { this.value = data; } } // Preorder traversal ( recursion ) public static
void preOrderRecur(Node head) { if (head == null) { return; }
preOrderRecur(head.right); } // Middle order traversal ( recursion ) public static void inOrderRecur(Node
head) { if (head == null) { return; } inOrderRecur(head.left);
System.out.print(head.value + " "); inOrderRecur(head.right); } // Postorder traversal ( recursion )
public static void posOrderRecur(Node head) { if (head == null) { return; }
System.out.print(head.value + " "); } // Preorder traversal ( non-recursive ) public static void
preOrderUnRecur(Node head) { System.out.print("pre-order: "); if (head != null)
{ Stack<Node> stack = new Stack<Node>(); stack.add(head); while
(!stack.isEmpty()) { head = stack.pop(); System.out.print(head.value + " "); if
(head.right != null) { stack.push(head.right); } if (head.left != null) {
stack.push(head.left); } } } System.out.println(); } // Middle order traversal ( non-recursive ) public static
void inOrderUnRecur(Node head) { System.out.print("in-order: "); if (head !=
null) { Stack<Node> stack = new Stack<Node>(); while (!stack.isEmpty() || head
!= null) { if (head != null) { stack.push(head); head = head.left; } else {
} System.out.println(); } // Postorder traversal ( non-recursive ) public static void posOrderUnRecur2(Node
head) { System.out.print("pos-order: "); if (head != null) { Stack<Node> s1 =
new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); s1.push(head); while
(!s1.isEmpty()) { head = s1.pop(); s2.push(head); if (head.left != null) {
s1.push(head.left); } if (head.right != null) { s1.push(head.right); } } while
(!s2.isEmpty()) { System.out.print(s2.pop().value + " "); } }
System.out.println(); } // Postorder traversal ( non-recursive ) public static void posOrderUnRecur2(Node h)
{ System.out.print("pos-order: "); if (h != null) { Stack<Node> stack = new
Stack<Node>(); stack.push(h); Node c = null; while (!stack.isEmpty()) { c =
stack.peek(); if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left); } else if (c.right != null && h != c.right) {
stack.push(c.right); } else { System.out.print(stack.pop().value + " "); h = c;
} } } System.out.println(); } // level traversal public static void levelTraverse(Node<T>
root){ if(root == null) return; Queue<Node<T>> queue = new
LinkedList<>();// Save the queue of nodes in sequence traversal queue.offer(root);// initialization while(!queue.isEmpty()){
BinaryNode<T> node = queue.poll(); System.out.print(node.element + " ");// Access node
if(node.left != null) queue.offer(node.left); if(node.right != null)
queue.offer(node.right); } }
<> Five , Ergodicity of Graphs
(1)BFS public static void bfs(Node node) { if (node == null) { return; }
Queue<Node> queue = new LinkedList<>(); HashSet<Node> map = new HashSet<>();
queue.add(node); map.add(node); while (!queue.isEmpty()) { Node cur =
queue.poll(); System.out.println(cur.value); for (Node next : cur.nexts) { if
(!map.contains(next)) { map.add(next); queue.add(next); } } } } (2) DFS public
static void dfs(Node node) { if (node == null) { return; } Stack<Node> stack =
new Stack<>(); HashSet<Node> set = new HashSet<>(); stack.add(node);
set.add(node); System.out.println(node.value); while (!stack.isEmpty()) { Node
cur = stack.pop(); for (Node next : cur.nexts) { if (!set.contains(next)) {