<>一、排序总结

(1) 快排 private void quicksort(int[] array, int begin, int end) { // TODO
Auto-generated method stub if(begin<end) { int key=array[begin]; //设置第一个元素为基准元素
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; //放置基准元素 quicksort(array,begin,i-1);
quicksort(array,i+1,end); } } } (2) 堆排序 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); } }
//建堆 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; } } //堆调整 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; } } //交换数据 public
static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j];
arr[j] = tmp; } (3) 归并排序 public static void mergeSort(int[] arr) { if (arr ==
null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); }
//归并具体操作 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); } //合并过程 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]; } }
<>二、查找总结

顺序查找:不需要数列本身有序,查找性能太差,平均查找长度为(1+n)/2,时间复杂度为O(n).
二分查找: 要求数列有序
行列递增的矩阵查找:按照杨氏矩阵特殊的存储方式
分块查找:顺序查找和二分查找的改进
其他查找算法:**深度优先查找、广度优先查找、二叉树查找(先、中、后、层序遍历)**等。
(1) 二分查找 /** * 递归实现的二分查找 * @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); } } /** * 二分查找的非递归实现 * @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; }
<>三、字符串匹配KMP
经典KMP 算法 //方法:获得模式串在母串的位置 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(); //主串字符串转数组 char[]ms=m.toCharArray(); //子串字符串转数组 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; } //获得模式串的next数组 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; }
<>四、二叉树的遍历
public static class Node { public int value; public Node left; public Node
right; public Node(int data) { this.value = data; } } //先序遍历(递归) public static
void preOrderRecur(Node head) { if (head == null) { return; }
System.out.print(head.value + " "); preOrderRecur(head.left);
preOrderRecur(head.right); } //中序遍历(递归) public static void inOrderRecur(Node
head) { if (head == null) { return; } inOrderRecur(head.left);
System.out.print(head.value + " "); inOrderRecur(head.right); } //后序遍历(递归)
public static void posOrderRecur(Node head) { if (head == null) { return; }
posOrderRecur(head.left); posOrderRecur(head.right);
System.out.print(head.value + " "); } //先序遍历(非递归) 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(); } //中序遍历(非递归) 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 {
head = stack.pop(); System.out.print(head.value + " "); head = head.right; } }
} System.out.println(); } //后序遍历(非递归) 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(); } //后序遍历(非递归) 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(); } //层序遍历 public static void levelTraverse(Node<T>
root){ if(root == null) return; Queue<Node<T>> queue = new
LinkedList<>();//层序遍历时保存结点的队列 queue.offer(root);//初始化 while(!queue.isEmpty()){
BinaryNode<T> node = queue.poll(); System.out.print(node.element + " ");//访问节点
if(node.left != null) queue.offer(node.left); if(node.right != null)
queue.offer(node.right); } }
<>五、图的遍历
(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)) {
stack.push(cur); stack.push(next); set.add(next);
System.out.println(next.value); break; } } } }

技术
©2019-2020 Toolsou All rights reserved,
python中delete怎么用_python中如何使用np.delete()方法?大厂Java岗春招必看:论一个面渣逆袭之路上必学得那些知识点3 4j不是合法的python表达式_3+4j不是合法的Python表达式。SQL综合题 员工单位综合题pyqt按钮调用python程序_PyQt:链接按钮到程序中的函数找出游戏的获胜者(java)看完这个去面试,稳过~~将硬盘转换成GPT分区格式python常用内置函数C语言(猜数字小游戏)