首页 > 代码库 > Java.utils.Collections学习

Java.utils.Collections学习

阅读类库代码是有意义的,尤其是Java集合类框架以及算法Collections Arrays都是值得阅读的,

一来可以减少新手程序员的编码的工作量,二来,对于常见的需求,程序员应该先找下是否有现成的类库

1.避免不必要的重复编码

2.自己编写的算法代码 容易出错,而且需要编写测试来保证正确性

3.使用类库的算法是业界一般做法

 

------------------------------------------------------------

 public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);//这里如果集合类实现了随机方法器,则使用二分搜索
        else
            return Collections.iteratorBinarySearch(list, key);//这里如果集合类没有实现随机访问,则使用迭代搜索
    }
//正常的二分搜索 复杂度为O(logn)就无需细究了
//我们来看迭代器的二分搜索实现

private static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        ListIterator<? extends Comparable<? super T>> i = list.listIterator();

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);//这里用了一个get方法
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }
//接上面,阅读get方法的代码
private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();//接上面,这里查找中间的值使用了O(n)的算法,所以对于链表等没有实现随机访问接口的容器来讲,查找依旧是O(n)
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }

 

 

 public static void reverse(List<?> list) 
//反序

 public static void shuffle(List<?> list) 
//洗牌

public static void shuffle(List<?> list, Random rnd) 
//洗牌 添加随机生成器,
//可惜这里没有使用用接口,而是具体的类Random
//这样就很难加入自己的随机数发生器了

public static void swap(List<?> list, int i, int j) 
//交换List集合中,两个元素的位置

private static void swap(Object[] arr, int i, int j) 
//交换对象数组中两个对象的位置

public static <T> void fill(List<? super T> list, T obj) 
//用一个对象填满集合

 

public static <T> void copy(List<? super T> dest, List<? extends T> src) 
//拷贝一个List集合中所有的对象的引用到另外一个List集合中,由于Java采用的是引用类型,所以修改一个List容器中的对象,另外容器对象的值也会改变,如果需要深度拷贝,应该自己编写代码 深度拷贝

public static void rotate(List<?> list, int distance) 
//旋转,从0-distance的元素将会被移动到List集合的末尾,List本身的长度不变
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
//使用replaceAll 记得覆盖对象的equals方法

 

Java.utils.Collections学习