算法算法算法算法

//二分查找
public class BinarySearch {

    public static  int binarySearch(int a[],int x,int n){
        int left=0;
        int right=n-1;
        while (left<=right){

            int mid=(left+right)/2;
            if (a[mid]==x)
                return mid;
            if (a[mid]>x)//左边
                right =mid-1;
            else  //右边
                left =mid+1;
        }
        return -1;//找不到
    }
}

//快速排序
public class QuickSort
{
  public static void quickSort(int a[],int p,int r){
      if (p<r){
          int q=partition(a,p,r);
          quickSort(a,p,q-1);
          quickSort(a,q+1,r);
      }
  }

    public static int partition(int a[],int p,int r){
      int i=p;
      int j=r+1;
      int t;
      int x=a[p];
      while (true){
          while (a[++i]<=x&&i<r);
          while (a[--j]>x);
          if (i>=j){
              break;
          }
          t=a[i];
          a[i]=a[j];
          a[j]=t;
      }
        a[p]=a[j];
        a[j]=x;
      return j;
    }

}

//归并排序
public class MergeSort {

  public static void mergeSort(int a[],int left,int right){
      if (left<right){
          int middle=(left+right)/2;
          mergeSort(a,left,middle);
          mergeSort(a,middle+1,right);
          merge(a,left,middle,right);
      }
  }

    private static void merge(int[] a, int left, int middle, int right) {
      int b[]=new int[right-left+1];
      int i=left;
      int j=middle+1;
      int k=0;
      while (i<=middle&&j<=right){
          if (a[i]<=a[j]){
              b[k++]=a[i++];
          }
          else {
              b[k++]=a[j++];
          }
      }

      while (i<=middle){
          b[k++]=a[i++];
      }
      while (j<=right){
          b[k++]=a[j++];
      }

        for (int m = 0; m < b.length; m++) {
            a[left+m]=b[m];
        }
    }


}

//二分搜索改写
public class TestBinary {
    public static int binarySearch(int a[],int x,int left,int right,int i,int j){
        int middle;
        while(left<=right){
            middle=(left+right)/2;
            if (x==a[middle]){//检查中间元素和目标值的大小
                i=j=middle;
                return 1;
            }
            if (x > a[middle]) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        i=right;
        j=left;
        return 0;
    }
}

//矩阵连乘
public class MatrixChain {
    //计算m[i][j]
    public static void matrixChain(int p[],int m[][],int s[][]){
        int n=p.length-1;
        for (int i = 1; i <=n; i++) {
            m[i][i]=0;
        }
        for (int r = 2; r <=n; r++) {
            for (int i = 1; i <=n-r+1; i++) {
                int j=i+r-1;
                m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j]=i;
                for (int k = i+1; k<j; k++) {
                    int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if (t<m[i][j]){
                        m[i][j]=t;
                        s[i][j]=i;
                    }
                }
            }
        }
    }
    public static void traceback(int i,int j,int s[][]){
        if (i==j){
            System.out.println("A"+i);
            return;
        }
        System.out.println("(");
        traceback(i,s[i][j],s);
        System.out.println(")");

        System.out.println("(");
        traceback(s[i][j]+1,j,s);
        System.out.println(")");
    }
}

//最长公共子序列
public class LCSLength {
    public static  void  LCSLength(int m,int n,char x[],char []y,int [][]c,int b[][]){
        int i,j;
        //当某一个序列是空的时候进行的操作
        for (i = 1;  i<=m; i++) {
            c[i][0] =0;
        }
        for (j = 1;  j<=n; j++) {
            c[0][j] =0;
        }
        //计算c[i][j]的值
        for (i = 1;  i<=m; i++) {
            for (j = 1;  j<=n; j++) {
                if (x[i]==y[j]){
                    c[i][j] = c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else if ( c[i-1][j]>= c[i][j-1]){
                    c[i][j] = c[i-1][j];
                    b[i][j]=2;
                }
                else {
                    c[i][j] = c[i][j-1];
                    b[i][j]=3;
                }
            }
        }
    }
    public static void  LCS(int i,int j,char x[],int b[][]){
        if (i==0||j==0){
            return;
        }

       if (b[i][j]==1){
           LCS(i-1,j-1,x,b);
       }
       else if (b[i][j]==2){
           LCS(i-1,j,x,b);
        }

       else {
           LCS(i,j-1,x,b);
       }
    }
}

//01背包
public class Knapsack {
    public static void knapsack(int v[],int w[],int c,int n,int m[][]){
        int jMax=Math.min(w[n-1],c);
        for (int j = 0; j <=jMax; j++) {
            m[n][j]=0;
        }
        for (int j = w[n]; j <=c ; j++) {
            m[n][j]=v[n];
        }

        for (int i = n-1; i >1 ; i--) {
            jMax=Math.min(w[i]-1,c );
            for (int j = 0; j <=jMax; j++) {
                m[i][j]=m[i+1][j];
            }
            for (int j = w[i]; j <=c ; j++) {
                m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
            }
        }
        m[1][c]=m[2][c];
        if (c>=w[1]){
            m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
        }
    }
    public static void traceback(int [][] m,int w[],int c,int n,int x[]){
        for (int i = 1; i <n; i++) {
            if (m[i][c]==m[i+1][c]){
                x[i]=0;
            }
            else {
                x[i]=1;
                c-=w[i];
            }
        }
        x[n]=m[n][c]>0?1:0;

    }
}

//改写快速排序
public class TestPartation {
    private static int Partition(int a[], int p, int r) {
        int i = p;
        int j = r + 1;
        int t;
        int x = a[p];
        while (true) {
            while (a[++i] >x && i < r);
            while (a[--j]<x);
            if (i>=j){
                break;
            }
            t=a[i] ;
            a[i]=a[j];
            a[j]=t;
        }
        a[p] = a[j];
        a[j] = x;
        return j;
    }
}