算法导论之随机算法

￡神魔★判官ぃ 2022-07-28 04:21 202阅读 0赞

**问题描述：**为了利用概率分析，我们需要了解关于输入分布的一些信息。在许多情况下，我们需要对输入分布了解的很少。即是知道输入分布的某些信息，也可能无法从计算上对该分布知识建立模型。然而，我们可以通过使一个算法的某部分的行为随机化，常可以利用概率和随机性作为算法设计和分析的工具。

**随机的算法：**如果一个算法的行为不仅仅由输入决定，而且也由随机数生成器产生的数决定，则称这个算法是随机的。

实现代码如下：

package algorithms;
    
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.TreeMap;
    
    
    public class PermuteBySorting {
    
    	public PermuteBySorting() {
    	}
    
    	public int[] randomSort(int[] A){
    		int[] B = new int[A.length];
    		for (int i = 0; i < B.length; i++) {
    			B[i] = (int) (Math.pow(A.length, 3)*Math.random());
    		}
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int i = 0; i < B.length; i++) {
    			map.put(B[i], A[i]);
    		}
    		map = sortMapByKey(map);
    		int i = 0;
    		for (int M : map.keySet()) {
    			A[i] = map.get(M);
    			i++;
    		}
    		return A;
    	}
    	
    	public static Map<Integer, Integer> sortMapByKey(Map<Integer, Integer> map) {
            if (map == null || map.isEmpty()) {
                return null;
            }
     
            Map<Integer, Integer> sortMap = new TreeMap<Integer, Integer>(
                    new MapKeyComparator());
     
            sortMap.putAll(map);
     
            return sortMap;
        }
    	public static void main(String[] args) {
    		int[] A = new int[]{1,2,3,4,5,6,7};
    		for (int i : new PermuteBySorting().randomSort(A)) {
    			System.out.println(i);
    		}
    
    	}
    
    }
    class MapKeyComparator implements Comparator<Integer>{
    	 
        @Override
        public int compare(Integer str1, Integer str2) {
             
            return str1.compareTo(str2);
        }
    }

上面的代码的功能是：输入一组数据，然后由随机生成器生成一组相应的优先级，然后根据这组优先级，对原数组进行排序。

在这里用的map，所以排序用的是Treemap，然后提供了一个比较器进行的排序。不能使用collections工具类。

原因如下：

Collection 
    ├List 
    │├LinkedList 
    │├ArrayList 
    │└Vector 
    │　└Stack 
    └Set 
    Map 
    ├Hashtable 
    ├HashMap 
    └WeakHashMap

如果想使用collections的方法的话，首先定义一个list，将map填入list，然后对list进行排序。代码如下：

ArrayList<Map.Entry<Integer, Integer>> l = new ArrayList<>(map.entrySet());
    Collections.sort(l, new Comparator<Map.Entry<Integer, Integer>>(){
    
    @Override
    public int compare(Entry<Integer, Integer> arg0,Entry<Integer, Integer> arg1) {
    	return arg0.getKey()-arg1.getKey();
    }});

上面代码可以根据key也可根据value进行排序。

以上是map排序的两种办法和随机算法的实现。