二分查找：

public class BinarySearch {//1、普通的二分查找public static int binarySearch(int[] arr,int target){if(arr.length==0) return -1;int left=0,right=arr.length-1;while(left<=right){int mid=left+(right-left)/2;if(arr[mid]==target){return mid;}else if(arr[mid]<target){left=mid+1;}else{right=mid-1;}}return -1;}//2、寻找左边界public static int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 别返回，锁定左侧边界right = mid - 1;}}// 最后要检查 left 越界的情况if (left >= nums.length || nums[left] != target)return -1;return left;}//3、寻找右边界public static int right_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 别返回，锁定右侧边界left = mid + 1;}}// 最后要检查 right 越界的情况if (right < 0 || nums[right] != target)return -1;return right;}
}

快排：

public class QuickSort {public static void quickSort(int[] array,int low,int high){if(low<high){//寻找基准数据的正确索引int index=getIndex(array,low,high);//分治quickSort(array,low,index-1);quickSort(array,index+1,high);}}public static int getIndex(int[] array,int low,int high){//基准数据int tmp=array[low];while(low<high){//当队尾的元素大于等于基准数据时，向前挪动high指针while(low<high&&array[high]>=tmp){high--;}// 如果队尾元素小于tmp了,需要将其赋值给lowarray[low]=array[high];// 当队首元素小于等于tmp时,向前挪动low指针while(low<high&&array[low]<=tmp){low++;}// 当队首元素大于tmp时,需要将其赋值给higharray[high]=array[low];}// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置array[low]=tmp;return low;}
}

归并排序：

public class MergeSort {public static int[] mergeSort(int[] array){if(array.length<2) return array;int mid=array.length/2;int[] left= Arrays.copyOfRange(array,0,mid);int[] right=Arrays.copyOfRange(array,mid,array.length);return merge(mergeSort(left),mergeSort(right));}public static int[] merge(int[] left,int[] right){int[] result=new int[left.length+right.length];for(int index=0,i=0,j=0;index<result.length;index++){if(i>=left.length)result[index]=right[j++];else if(j>=right.length)result[index]=left[i++];else if(left[i]>right[j])result[index]=right[j++];elseresult[index]=left[i++];}return result;}
}

堆排序：

public class HeapSort {public static int len;public static int[] heapSort(int[] array){len=array.length;if(len<1) return array;//构建最大堆buildMaxHeap(array);//依次将最大堆的元素移至数组尾部，并维护最大堆while(len>0){int temp=array[len-1];array[len-1]=array[0];array[0]=temp;len--;adjustHeap(array,0);}return array;}public static void buildMaxHeap(int[] array){len= array.length;//从最后一个非叶子节点开始向上构造最大堆for (int i = (len/2- 1); i >= 0; i--) {adjustHeap(array, i);}}public static void adjustHeap(int[] array, int i) {//指向最大值的指针int maxIndex = i;//i的左子树和右子树分别2i+1和2(i+1)int left=i * 2 + 1;int right=i * 2 + 2;//如果有左子树，且左子树大于父节点，则将最大指针指向左子树if (left < len && array[left] > array[maxIndex])maxIndex = left;//如果有右子树，且右子树大于父节点，则将最大指针指向右子树if (right < len && array[right] > array[maxIndex])maxIndex = right;//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。if (maxIndex != i) {int temp=array[maxIndex];array[maxIndex]=array[i];array[i]=temp;adjustHeap(array, maxIndex);}}
}

树的三种遍历（递归和迭代）：

二叉树的前序遍历：根 左 右
递归

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();preorder(root,res);return res;}public void preorder(TreeNode root,List<Integer>list){if(root==null) return;list.add(root.val);preorder(root.left,list);preorder(root.right,list);}
}

迭代：队列存取右子树

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();Deque<TreeNode>stack=new LinkedList<>();TreeNode temp=root;while(temp!=null||!stack.isEmpty()){while(temp!=null){stack.addFirst(temp.right);res.add(temp.val);temp=temp.left;}temp=stack.removeFirst();}return res;}
}

二叉树的中序遍历：左 根 右
递归

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();preorder(root,res);return res;}public void preorder(TreeNode root,List<Integer>list){if(root==null) return;preorder(root.left,list);list.add(root.val);preorder(root.right,list);}
}

迭代：队列存取根

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();Deque<TreeNode>queue=new LinkedList<>();TreeNode temp=root;while(temp!=null||!queue.isEmpty()){while(temp!=null){queue.addFirst(temp);temp=temp.left;}temp=queue.removeFirst();res.add(temp.val);temp=temp.right;}return res;}
}

二叉树的后序遍历：左 右 根
递归

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();preorder(root,res);return res;}public void preorder(TreeNode root,List<Integer>list){if(root==null) return;preorder(root.left,list);preorder(root.right,list);list.add(root.val);}
}

迭代，后续遍历结果的逆序为根 右 左，参考前序遍历根 左 右

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer>res=new ArrayList<>();Deque<TreeNode>queue=new LinkedList<>();TreeNode temp=root;while(temp!=null||!queue.isEmpty()){while(temp!=null){queue.addFirst(temp.left);res.add(temp.val);temp=temp.right;}temp=queue.removeFirst();}Collections.reverse(res);return res;}
}