冒泡算法的小变种

冒泡算法大家都见得多啦，笔试也经常出，但更多的题目可能会加多一些限制条件。下面举2个例子，这方面做得少的朋友可以以此打开一下思维，其实原理都是一样的。如果有其他的例子或者更好的做法，希望可以提出来，和大家一起分享下:)

题目1：从小到大排列下面一堆数字，3,1,6,2,9,0,2,3,9,3,9 ..并且打印他们重复的次数(先不要急着看答案，自己想一下，能想出更好的做法^_^)


参考代码如下：

import java.util.*;

public class Test2 {
      public static void main(String[] args) {
		int[] values = {3,1,6,2,9,0,2,3,9,3,9};
		sort(values);

	}
      public static void sort(int[] vaa){
    	  
    	  //用于交换
    	  int temp;
    	  //Map是用于存放每个数与他的出现次数(数为key,出现次数是value)
    	  Map<Integer,Integer> m = new HashMap<Integer,Integer>();

    	  int[] arrays = vaa;
    	  for(int i=0;i<arrays.length;i++){
    		  for(int j=0;j<arrays.length-i-1;j++){
    			  
    			  if(arrays[j]>arrays[j+1]){
    				  temp = arrays[j];
    				  arrays[j] = arrays[j+1];
    				  arrays[j+1] = temp;
    			  }    			 
    		  }
    	  }
    	  
    	  for(int i=0;i<arrays.length;i++){
    		  System.out.print(arrays[i]+",");
    	  }
    	  
    	  //计算每个数的重复次数
    	  for(int i = 0;i<arrays.length;i++){
    		  if(!m.containsKey(arrays[i])){
    			  m.put(arrays[i], 1);
    		  }
    		  else{
    			  int a = (Integer)m.get(arrays[i]);
    			  a=a+1;
    			  m.remove(arrays[i]);
    			  m.put(arrays[i], a);
    		  }
    	  }
    	  System.out.println("长度:"+arrays.length);
    	  
    	  //加到Set里面过滤一下重复数字，TreeSet是为了打印出来按顺序好看点
    	  Set<Integer> set = new TreeSet<Integer>();
    	  for(int i=0;i<arrays.length;i++){
    		  set.add(arrays[i]);
    	  }

    	  for(int i:set){
    		  System.out.println(i+",重复次数是："+(m.get(i)-1));
    	  }
      }    
}

小结：我的做法用Map来记录每个数的重复次数，不一定是最好和最快的。




题目二：从大到小排列下面这些数("5-1-9","5-2-5","5-2-4","5-3-1", "8-1-5"),要求当第一个数相等的时候比较第2个，当第二个相等的时候比较第3个


参考代码如下：

public class StringSort1 {
	public static void main(String[] args) {
		String[] str = {  "5-1-9","5-2-5","5-2-4","5-3-1", "8-1-5" };
		sort(str);
		System.out.println("最后结果为：");
		for(int i=0;i<str.length;i++){
			System.out.println(str[i]);
		}
	}

	public static String[] sort(String[] str) {
		int count=0;
		//冒泡算法：2个for循环
        for(int i=0;i<str.length;i++){
        	for(int j=0;j<str.length-i-1;j++){       		
        	count++;	
        	
        	//解析相邻两个数并比较大小
        	String[] s = str[j].split("-");        	
        	int[] first = new int[3];
        	first[0] = Integer.parseInt(s[0]);
        	first[1] = Integer.parseInt(s[1]);
        	first[2] = Integer.parseInt(s[2]);
        	
        	String[] s2 = str[j+1].split("-");
        	int[] second = new int[3];
        	second[0] = Integer.parseInt(s2[0]);
        	second[1] = Integer.parseInt(s2[1]);
        	second[2] = Integer.parseInt(s2[2]);
        	
        	//比较3种情况进行交换:
        	String temp;
        	if(first[0]<second[0] || (first[0]==second[0] && first[1]<second[1]) ||
        			( first[0]==second[0] && first[1]==second[1] && first[2]<second[2])){
        		temp = str[j];
        		str[j] = str[j+1];
        		str[j+1] = temp;
        	}     	       	
          }
        }		
        System.out.println("遍历了"+count+"次");
		return str;
	}
}

小结：这题更简单，只需要在排列的时候把他们一个一个拿出来，然后比较的时候按3种情况就OK了
希望大家提出更多更好的例子