常用算法汇总

快速排序

• 注：若排序是有序的，采用快排，则退化为冒泡排序。

解决这个问题，采用两个选取基准的方法:
（1）随机选取基数（在这个区间内随机取一个数）
出现的恶劣情况是整个数组全相等，还是退化为冒泡排序
（2）三数取中法
把待排序列分成等长的子序列，最佳的是取中间数为基准
举例：待排序序列为：8 1 4 9 6 3 5 2 7 0
左边为：8，右边为0，中间为6.
我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6

四种优化方式：

• 优化方式1：插排
  当待排序序列的长度分割到一定大小后（如子序列长度小于10），使用插入排序
• 优化方式2：聚集相等元素
• 优化方式3：采用尾递归
• 优化方式4:采用并行或多线程处理子序列

堆排序

全排列

/**
	 * 字符串的排列：（考察的知识点就是全排列）
	 * 输入字符： a b c
	 * 输出字符：abc ,acb,bac,bca,cab,cba
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String str=sc.next();
			ArrayList<String> re=Permutation(str);
			for(String s:re){
				System.out.println(s);
			}
		}

	}
	public static ArrayList<String> Permutation(String str) {
	     ArrayList<String> re=new ArrayList<String>();
	     if(str==null||str.length()==0){
	    	 return re;
	     }
			HashSet<String> set=new HashSet<String>();
			fun(set,str.toCharArray(),0);
			re.addAll(set);//将出现的字符串保存在list集合中
			Collections.sort(re);
			return re;
			
		}
	static void  fun(HashSet<String> re,char[] str, int k){
		if(k==str.length){
			re.add(new String(str));
			return;
		}
		for(int i=k;i<str.length;i++){//在for循环中，第一次初始化，然后判断，执行for循环体。执行完后i+1,在判断（初始化只执行一次）
			swap(str,i,k);
			fun(re,str,k+1);
			swap(str,i,k);//防止元素的重复，进行复原
			}
}
	//将数组中的两个数进行交换
	static void   swap(char[] str,int i,int j){
		if(i!=j){//相同就不用交换了
			char t=str[i];
			str[i]=str[j];
			str[j]=t;
		}
	}    
   }

二进制数中1的个数（用与运算）

static int  NumberOf3(int n) {
		int count=0;
		while(n!=0){//整数不为0，必有1
			++count;
			n=n&(n-1);
			
		}
		return count;
	}

反转二叉树（就是二叉树的镜像）

public void Mirror(TreeNode root) {
	 if(root==null) {//为空结点
  	   return;
     }
     if(root.left==null&&root.right==null){//表明该结点是叶子节点或只是根为的节点
  	   return;
     }
     //交换当前节点的左右子树
     TreeNode temp;
     temp=root.left;
     root.left=root.right;
     root.right=temp;
     if(root.left!=null){
  	   Mirror(root.left);
     }
     if(root.right!=null){
  	   Mirror(root.right);
     }
	}

通过前序、中序，重建二叉树

/**
	 * 解题的步骤:
	 * 1：递归的结束条件，只有到叶子节点，递归才结束（preStart==preEnd&&inStart==inEnd）
	 * 2:在中序中找到根，通过根算出左子树的长度，右子树的长度（左右子树各有多少个节点）
	 * 3：通过左子树的长度，算出前序左子树的起始节点（preStart+1,preStart+leftTree），中序左子树的起始节点（inStart,root-1），递归前提条件是leftLength>0（若为0，那就是叶子节点了）
	 * 4:同上算出右子树的递归
	 */
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    	if(pre==null||in==null){//只要一个为空，另一个必为
    		return null;
    	}
    	TreeNode root=binaryTree(pre,in,0,pre.length-1,0,in.length-1);
    	return root;
    }
    public TreeNode binaryTree(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd){
    	//构造一个结点
    	TreeNode node=new TreeNode(pre[preStart]);
    	node.left=null;
    	node.right=null;
    	//现在要想想递归的结束条件是什么，preStart=preEnd和inStart=inEnd,表明这是一个叶子节点
    	if(preStart==preEnd&&inStart==inEnd){
    		return node;
    	}
    	//现在要找出根节点
    	int root=0;
    	//肯定在in数组中找了
    	for(int i=inStart;i<in.length;i++){
    		if(pre[preStart]==in[i]){
    			root=i;
    			break;
    		}
    	}
    	//找到根节点，就得算出左右子树的长度(肯定是通过in数组)
    	int leftTree=root-inStart;//要去掉根节点即第一个节点
    	int rightTree=inEnd-root;
    	if(leftTree>0){
    		node.left=binaryTree(pre,in,preStart+1,preStart+leftTree,inStart,root-1);
    	}
    	if(rightTree>0){
    		node.right=binaryTree(pre, in, preStart+leftTree+1, preEnd, root+1, inEnd);
    	}
    	
    	
    	return node;
    }
}

动态规划

  动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解决由上一次子问题的解推出。

贪心算法：

  每次选最大的，然后选择第二大的，在选第三大的，……，直到满足条件后结束或到最后也不能满足条件结束。