冒泡排序

  1. package com.company;
  3. public class Main {
  4.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  5.     public static void main(String[] args) {
  6.         for (int i = 0; i < a.length-1; i++) {
  7.             for (int j=1;j<a.length-i;j++){
  8.                 if (a[j-1]>a[j]){
  9.                     a_swap(j-1,j);
  10.                 }
  11.             }
  12.         }
  13.         a_printf();
  14.     }
  15.     public static void a_swap(int index_a,int index_b){
  16.         int temp=a[index_a];
  17.         a[index_a]=a[index_b];
  18.         a[index_b]=temp;
  19.     }
  21.     public static void a_printf(){
  22.         for (int value : a) {
  23.             System.out.print(value + " ");
  24.         }
  25.     }
  26. }

选择排序

  1. package com.company;
  3. public class Main {
  4.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  5.     public static void main(String[] args) {
  6.         for (int i = 0; i < a.length; i++) {
  7.             int max=0;
  8.             for(int j=0;j<a.length-i;j++){
  9.                 if(a[max]<a[j]){
  10.                     max=j;
  11.                 }
  12.             }
  13.             a_swap(max,a.length-i-1);
  14.         }
  16.         a_printf();
  17.     }
  18.     public static void a_swap(int index_a,int index_b){
  19.         int temp=a[index_a];
  20.         a[index_a]=a[index_b];
  21.         a[index_b]=temp;
  22.     }
  24.     public static void a_printf(){
  25.         for (int value : a) {
  26.             System.out.print(value + " ");
  27.         }
  28.     }

插入排序

  1. package com.company;
  3. public class Main {
  4.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  5.     public static void main(String[] args) {
  6.         for (int i =1; i < a.length; i++) {
  7.             for(int j=i-1;j>0;j--){
  8.                 if (a[j]>a[j+1]){
  9.                     a_swap(j,j+1);
  10.                 }
  11.             }
  13.         }
  14.         a_printf();
  15.     }
  16.     public static void a_swap(int index_a,int index_b){
  17.         int temp=a[index_a];
  18.         a[index_a]=a[index_b];
  19.         a[index_b]=temp;
  20.     }
  22.     public static void a_printf(){
  23.         for (int value : a) {
  24.             System.out.print(value + " ");
  25.         }
  26.     }
  27. }

二分查找

  1. static int[] a_order=new int[]{3,9,11,12,14,18,53,61,65,89};
  2.     public static void main(String[] args) {
  3.         Scanner scanner=new Scanner(System.in);
  4.         int minNum=scanner.nextInt();
  5.         int left=0,right=a_order.length-1,min=0;
  6.         while (left<=right){
  7.             min=(left+right)/2;
  8.             if (a_order[min]==minNum){
  9.                 System.out.println("get");
  10.                 return;
  11.             }else if (a_order[min]>minNum){
  12.                 right=min-1;
  13.             }else {
  14.                 left=min+1;
  15.             }
  17.         }
  18.         System.out.println("don't get");
  20.     }

归并排序

递归

  1. package com.company;
  4. public class Main {
  5.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  6.     static int[] a_order=new int[]{3,9,11,12,14,18,53,61,65,89};
  7.     public static void main(String[] args) {
  8.         mergeSort(0,a.length-1);
  9.         a_printf();
  10.     }
  12.     public static void mergeSort(int left,int right){
  13.         if (left<right){
  14.             int mid=(left+right)/2;
  15.             mergeSort(left,mid);
  16.             mergeSort(mid+1,right);
  17.             merge(left,mid,mid+1,right);
  18.         }
  19.     }
  21.     //[l1,r1]+[l2,r2]
  22.     public static void merge(int l1,int r1,int l2,int r2){
  23.         int i=l1,j=l2,index=0;
  24.         int[] temp=new int[10];//tenp临时存放合并后的数组，index为其下标
  25.         while (i<=r1&&j<=r2){
  26.             if (a[i]<=a[j]){
  27.                 temp[index++]=a[i++];
  28.             }else {
  29.                 temp[index++]=a[j++];
  30.             }
  31.         }
  32.         while (i<=r1) temp[index++]=a[i++];
  33.         while (j<=r2) temp[index++]=a[j++];
  34.         for (i = 0; i < index; i++) {
  35.             a[l1+i]=temp[i];
  36.         }
  37.     }
  39.     public static void a_swap(int index_a,int index_b){
  40.         int temp=a[index_a];
  41.         a[index_a]=a[index_b];
  42.         a[index_b]=temp;
  43.     }
  45.     public static void a_printf(){
  46.         for (int value : a) {
  47.             System.out.print(value + " ");
  48.         }
  49.     }
  50. }

非递归

  1. package com.company;
  4. public class Main {
  5.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  6.     static int[] a_order=new int[]{3,9,11,12,14,18,53,61,65,89};
  7.     public static void main(String[] args) {
  8.         mergeSort();
  9.         a_printf();
  10.     }
  12.     public static void mergeSort(){
  13.         //step为组内元素个数,step/2为左子空间元素个数，注意等号可以不取
  14.         for (int step=2;step/2<=10;step*=2){
  15.             //每step个元素一组，组内前step/2和后step/2个元素进行合并
  16.             for (int i=0;i<10;i+=step){//对每一组
  17.                 int mid=i+step/2-1;//左子区间元素个数为step/2
  18.                 if (mid+1<10){//有子区间存在元素则合并
  19.                     //左子空间为[i,mid] , 右子空间为[mid+1,min(i+step-1,n)]
  20.                     merge(i,mid,mid+1,Integer.min(i+step-1,9));
  21.                 }
  23.             }
  24.         }
  25.     }
  27.     //[l1,r1]+[l2,r2]
  28.     public static void merge(int l1,int r1,int l2,int r2){
  29.         int i=l1,j=l2,index=0;
  30.         int[] temp=new int[10];//tenp临时存放合并后的数组，index为其下标
  31.         while (i<=r1&&j<=r2){
  32.             if (a[i]<=a[j]){
  33.                 temp[index++]=a[i++];
  34.             }else {
  35.                 temp[index++]=a[j++];
  36.             }
  37.         }
  38.         while (i<=r1) temp[index++]=a[i++];
  39.         while (j<=r2) temp[index++]=a[j++];
  40.         for (i = 0; i < index; i++) {
  41.             a[l1+i]=temp[i];
  42.         }
  43.     }
  45.     public static void a_swap(int index_a,int index_b){
  46.         int temp=a[index_a];
  47.         a[index_a]=a[index_b];
  48.         a[index_b]=temp;
  49.     }
  51.     public static void a_printf(){
  52.         for (int value : a) {
  53.             System.out.print(value + " ");
  54.         }
  55.     }
  56. }

快速排序

  1. package com.company;
  4. public class Main {
  5.     static int[] a=new int[]{3,61,14,53,65,12,89,18,11,9};
  6.     static int[] a_order=new int[]{3,9,11,12,14,18,53,61,65,89};
  7.     public static void main(String[] args) {
  8.         quickSort(0,9);
  9.         a_printf();
  10.     }
  12.     public static void quickSort(int left,int right){
  13.         if (left<right){ //当前区间长度超过1
  14.             //将[left,right]按a[left]一分为二
  15.             int pos=Partition(left,right);
  16.             quickSort(left,pos-1); //对左子区间递归进行快速排序
  17.             quickSort(pos+1,right); //对右子区间递归进行快速排序
  18.         }
  19.     }
  21.     public static int Partition(int left,int right){
  22.         int temp=a[left];//将a[left]存放在临时变量temp
  23.         while (left<right){ //只要left与right不相遇
  24.             while (left<right&&a[right]>temp) right--; //反复左移right
  25.             a[left]=a[right];   //将a[right]挪到a[left]
  26.             while (left<right&&a[left]<=temp) left++; //反复右移left
  27.             a[right]=a[left];   //将a[left]挪到a[right]
  28.         }
  29.         a[left]=temp; //把temp放到left与right相遇的地方
  30.         return left; //返回相遇的下标
  31.     }
  34.     public static void a_swap(int index_a,int index_b){
  35.         int temp=a[index_a];
  36.         a[index_a]=a[index_b];
  37.         a[index_b]=temp;
  38.     }
  40.     public static void a_printf(){
  41.         for (int value : a) {
  42.             System.out.print(value + " ");
  43.         }
  44.     }
  45. }

深度优先搜索

  1. package com.company;
  3. import java.util.Scanner;
  5. public class Main {
  6.     static int n,V,maxValue=0; //物品件数n，背包容量v，最大价值maxValue
  7.     static int[] w=new int[30],c=new int[30]; //w[i]为每件物品的重量，c[i]为每件物品的价值
  8.     public static void main(String[] args) {
  9.         initData();
  10.         DFS(0,0,0);
  11.         System.out.println(maxValue);
  12.     }
  14.     private static void initData() {
  15.         Scanner scanner=new Scanner(System.in);
  16.         System.out.println("cin n:");
  17.         n=scanner.nextInt();
  18.         System.out.println("cin V:");
  19.         V=scanner.nextInt();
  20.         System.out.println("cin w[i]:");
  21.         for (int i = 0; i < n; i++) {
  22.             w[i]=scanner.nextInt();
  23.         }
  24.         System.out.println("cin c[i]:");
  25.         for (int i = 0; i < n; i++) {
  26.             c[i]=scanner.nextInt();
  27.         }
  28.     }
  30.     //DFS ,index为当前处理的物品编号
  31.     //sumW和sumC分别为当前总重量和当前总价值
  32.     public static void DFS(int index,int sumW,int sumC){
  33.        if (index==n){ //已经完成对n件物品的选择（死胡同）
  34.             return;
  35.         }
  36.         //岔道口
  37.         DFS(index+1,sumW,sumC);//不选第index件物品
  38.         //只有加入第index件物品后未超过容量v，才能继续
  39.         if (sumW + w[index] <= V) {
  40.             if (sumC+c[index]>maxValue){
  41.                 maxValue=sumC+c[index]; //更新最大价值maxValue
  42.             }
  43.         }
  44.         DFS(index+1,sumW+w[index],sumC+c[index]); //选第index件物品
  45.     }
  48. }
  1. cin n:
  2. 5
  3. cin V:
  4. 8
  5. cin w[i]:
  6. 3 5 1 2 2
  7. cin c[i]:
  8. 4 5 2 1 3
  10. maxValue:10

树的遍历

  1. package com.company;
  3. public class Node {
  4.     private Integer id;
  5.     private Node left;
  6.     private Node right;
  8.     public Node(Integer id) {
  9.         this.id = id;
  10.     }
  12.     public Integer getId() {
  13.         return id;
  14.     }
  16.     public void setId(Integer id) {
  17.         this.id = id;
  18.     }
  20.     public Node getLeft() {
  21.         return left;
  22.     }
  24.     public void setLeft(Node left) {
  25.         this.left = left;
  26.     }
  28.     public Node getRight() {
  29.         return right;
  30.     }
  32.     public void setRight(Node right) {
  33.         this.right = right;
  34.     }
  36.     public Node(Integer id, Node left, Node right) {
  37.         this.id = id;
  38.         this.left = left;
  39.         this.right = right;
  40.     }
  41. }

递归遍历（前中后）

  1. package com.company;
  3. public class Tree {
  4.     private Node root;
  6.     public Tree() {
  7.         build();
  8.     }
  10.     /**
  11.      * 建树 【V80】
  12.      *
  13.      *              1
  14.      *         2         3
  15.      *           4      5  6
  16.      *                7
  17.      */
  18.     public void build() {
  19.         Node node7 = new Node(7);
  20.         Node node6 = new Node(6);
  21.         Node node5 = new Node(5, node7, null);
  22.         Node node4 = new Node(4);
  23.         Node node3 = new Node(3, node5, node6);
  24.         Node node2 = new Node(2, null, node4);
  25.         root = new Node(1, node2, node3);
  26.     }
  28.     //前序遍历
  29.     public void DLR(Node root){
  30.         if (root==null){
  31.             return;
  32.         }
  33.         System.out.print(root.getId()+" ");
  34.         DLR(root.getLeft());
  35.         DLR(root.getRight());
  36.     }
  38.     //中序遍历
  39.     public void LDR(Node root){
  40.         if (root==null){
  41.             return;
  42.         }
  43.         LDR(root.getLeft());
  44.         System.out.print(root.getId()+" ");
  45.         LDR(root.getRight());
  46.     }
  47.     //后序遍历
  48.     public void LRD(Node root){
  49.         if (root==null){
  50.             return;
  51.         }
  52.         LRD(root.getLeft());
  53.         LRD(root.getRight());
  54.         System.out.print(root.getId()+" ");
  55.     }
  56.     public Node getRoot() {
  57.         return root;
  58.     }
  60.     public void setRoot(Node root) {
  61.         this.root = root;
  62.     }
  63. }

非递归遍历（前中后）

  1. package com.company;
  3. import java.util.*;
  5. public class UDTree {
  6.     private Node root;
  8.     public UDTree() {
  9.         build();
  10.     }
  12.     /*非递归先序遍历
  13.     * 这里的思路是利用栈先进后出的性质，先将根节点入栈
  14.     * 循环中，弹出根节点，然后先加入右子节点，后加入左子节点
  15.     * 再一次循环，新弹出的节点就是刚压入的左子节点
  16.     * */
  17.     public void DLR(Node root){
  18.         if (root == null) {
  19.             return;
  20.         }
  21.         Stack<Node> stack=new Stack<>();
  22.         stack.push(root);
  23.         while (!stack.isEmpty()){
  24.             Node top=stack.pop();
  25.             System.out.print(top.getId()+" ");
  26.             if (top.getRight()!=null)
  27.                 stack.push(top.getRight());
  28.             if (top.getLeft()!=null)
  29.                 stack.push(top.getLeft());
  30.         }
  31.     }
  32.     //非递归中序遍历 中序遍历是 左 根 右
  33.     public void LDR(Node root){
  34.         if (root == null) {
  35.             return;
  36.         }
  37.         Stack<Node> stack=new Stack<>();
  38.         while (root!=null||!stack.isEmpty()){
  39.             while (root!=null){
  40.                 stack.push(root);
  41.                 root=root.getLeft();
  42.             }
  43.             if (!stack.isEmpty()){
  44.                 root=stack.pop();
  45.                 System.out.print(root.getId()+" ");
  46.                 root=root.getRight();
  47.             }
  48.         }
  49.     }
  50.     //非递归后序遍历 由于后序遍历二叉树的顺序是 左 右 根，故可以使用中间临时栈保存 根 右 左 的遍历结果
  51.     public void LRD(Node root){
  52.         if (root==null)
  53.             return;
  54.         Stack<Node> stack=new Stack<>();
  55.         Stack<Node> stack1=new Stack<>();
  56.         while (root!=null||!stack.isEmpty()){
  57.             while (root!=null){
  58.                 stack.push(root);
  59.                 stack1.push(root);
  60.                 root=root.getRight();
  61.             }
  62.             if (!stack.isEmpty()){
  63.                 root=stack.pop();
  64.                 root=root.getLeft();
  65.             }
  66.         }
  67.         while (!stack1.isEmpty()){
  68.             System.out.print(stack1.pop().getId()+" ");
  69.         }
  70.     }
  72.     public void build() {
  73.         Node node7 = new Node(7);
  74.         Node node6 = new Node(6);
  75.         Node node5 = new Node(5, node7, null);
  76.         Node node4 = new Node(4);
  77.         Node node3 = new Node(3, node5, node6);
  78.         Node node2 = new Node(2, null, node4);
  79.         root = new Node(1, node2, node3);
  80.     }
  82.     public Node getRoot() {
  83.         return root;
  84.     }
  86.     public void setRoot(Node root) {
  87.         this.root = root;
  88.     }
  89. }

层次遍历

  1.  public void LevelOrder(Node root){
  2.         if (root == null) {
  3.             return;
  4.         }
  5.         Queue<Node> queue=new LinkedList<>();
  6.         queue.add(root);
  7.         while (!queue.isEmpty()){
  8.             root=queue.poll();
  9.             System.out.print(root.getId()+" ");
  10.             if (root.getLeft() != null) {
  11.                 queue.add(root.getLeft());
  12.             }
  13.             if (root.getRight() != null) {
  14.                 queue.add(root.getRight());
  15.             }
  16.         }
  17.     }