几种比较常见的算法排序

归并排序

    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

public class Solution {
    int cnt;
    public int InversePairs(int [] array) {
        cnt = 0;
        if (array != null)
            mergeSortUp2Down(array, 0, array.length - 1);
        return cnt;
    }
 public void mergeSortUp2Down(int[] a, int start, int end) {
        if (start >= end)
            return;
        int mid = (start + end) >> 1;
 
        mergeSortUp2Down(a, start, mid);
        mergeSortUp2Down(a, mid + 1, end);
 
        merge(a, start, mid, end);
    }
    public void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];
 
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                tmp[k++] = a[j++];
                cnt =(cnt+ mid - i + 1)%1000000007; 
            }
        }
        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];
        for (k = 0; k < tmp.length; k++)
            a[start + k] = tmp[k];
    }
}

 针对上面同一问题

冒泡排序

 public class Solution {
      public int InversePairs(int [] number) {
        int count=0; 5         
 4          for(int i1=0;i1<number.length;i1++){
            for(int j=i1;j<number.length;j++){
                if(number[i1]>number[j]){
                    count++;
                }
            }
        }
          return count;
    }
}

插入排序

 public class Solution {
      public int InversePairs(int [] number) {
          int count1 = 0;
        for(int i1=1;i1<number.length;i1++){
            int temp = number[i1];
            int j=i1;
            while(j>0&&temp<number[j-1]){
                number[j] = number[j-1];
                number[j-1] = temp;
                count1++;
                j--;
            }
        }
          return count1;
    }
}

回溯法

   输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> list = new ArrayList<String>();
        if(str == null||str.length()==0)
            return list;
       TreeSet<String> set = new TreeSet<String>();
        fun(set,str.toCharArray(),0);
        list.addAll(set);
        return list;
    }
    public void fun(TreeSet set,char[] str,int k){
        if(str.length == k){
            set.add(new String(str));
            return;
        }
        for(int i=k;i<str.length;i++){
            swap(str,i,k);
                fun(set,str,k+1);
            swap(str,i,k);
        }
    }
    public void swap(char[] str,int i,int j){
            if(i!=j){
                char t = str[i];
                str[i] = str[j];
                str[j] = t;
            }
        }
}

插入排序

    输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution {
    public void reOrderArray(int [] array) {
        int temp;
        int index;
        for(int i=0;i<array.length;i++){
            if((array[i]&1)==1){
                temp = array[i];
                index = i-1;
                while(index>=0 && array[index]%2==0){
                    array[index+1]=array[index];
                    index--;
                }
                array[index+1]=temp;
            }
        }
    }
}

递归排序

   输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result=false;
        if(root2 == null || root1 == null)
            return false;
        if(root1.val == root2.val){
            result = isSubtree(root1,root2);
        }
        if(!result){
            result = HasSubtree(root1.left,root2);
        }
        if(!result){
            result = HasSubtree(root1.right,root2);
        }
        return result;
    }
     public static boolean isSubtree(TreeNode root1,TreeNode root2){
        if(root2 == null)
            return true;
         if(root1 == null)
             return false;
         if(root1.val != root2.val)
             return false;
         return isSubtree(root1.left,root2.left)&&isSubtree(root1.right,root2.right);
    }
}