java.util.Collections工具包

java.util.Collections: Java集合框架的一个工具类，提供Collection通用算法: 排序、二分查找、洗牌等

`Collections.sort` 排序

默认排列(正序): Collections.sort(list);

Comparator 排序:

Collections.sort(list, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }
});

使用 o2 和 o1 进行做对比，输出倒叙排序
Comparator 可以对对象类按照某个字段进行排序

reverseOrder 倒排: Collections.sort(list, Collections.<String>reverseOrder());

源码

Collections.sort : 集合排序，最终使用的方法为Arrays.sort((E[]) elementData, 0, size, c);

public static <T> void sort(T[] a, int fromIndex, int toIndex,
                            Comparator<? super T> c) {
    if (c == null) {
        sort(a, fromIndex, toIndex);
    } else {
        rangeCheck(a.length, fromIndex, toIndex);
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex, c);
        else
            TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
    }
}

包括旧版的归并排序 legacyMergeSort 和 TimSort 排序
因为开关的关系(LegacyMergeSort.userRequested = false)，基本都是走到 TimSort 排序
在排序的过程中会因为元素个数是否大于32而选择分段排序和二分插入排序

`Collections.binarySearch` 二分查找

二分查找: 二分查找的前提是集合有序

源码

Collections.binarySearch

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);
}

list instanceof RandomAccess: ArrayList 有实现 RandomAccess，但是 LinkedList 并没有
BINARYSEARCH_THRESHOLD = 5000: 元素阈值的校验，小于这个范围的都用 indexedBinarySearch 进行查找

Collections.indexedBinarySearch(list, key):

private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        Comparable<? super T> midVal = list.get(mid);
        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
}

耗时点在于 list.get(mid)

Collections.iteratorBinarySearch(list, key):

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);
        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
}

元素数量大于5000个，并且是LinkedList是会使用迭代器 list.listIterator 的方式进行二分查找，但是对于链表的数据结构，仍然没有数组二分处理的速度快，主要原因在获取元素的时间复杂度上

`Collections.shuffle` 洗牌算法

将集合中的元素进行打乱，一般可以用在抽奖、要好、洗牌等场景
1. Collections.shuffle(list);: 直接传入集合
2. Collections.shuffle(list, new Random(100));: 传入固定的随机种子，这种方式可以控制洗牌范围

源码

Random random = new Random();
for (int i = list.size(); i > 1; i--) {
    int ri = random.nextInt(i);  // 随机位置
    int ji = i - 1;              // 顺延
    System.out.println("ri：" + ri + " ji：" + ji);
    list.set(ji, list.set(ri, list.get(ji)));        // 元素置换
}

通过随机数，从逐渐缩小范围的集合中找到对应的元素，与递减的下标位置进行元素替换
洗牌算法

`Collections.rotate` 旋转算法

把 ArrayList 或者 LinkedList，从指定的某个位置开始，进行正旋或者逆旋操作

源码

旋转算法的实现类分为两部分:

为 ArrayList 或者元素数量不多(ROTATE_THRESHOLD = 100)时，通过 rotate1 实现
为 LinkedList 并且元素数量超过 ROTATE_THRESHOLD 时，通过 rotate2 实现

public static void rotate(List<?> list, int distance) {
    if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
        rotate1(list, distance);
    else
        rotate2(list, distance);
}

rotate1:

private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;
    if (distance == 0)
        return;
    for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int i = cycleStart;
        do {
            i += distance;
            if (i >= size)
                i -= size;
            displaced = list.set(i, displaced);
            nMoved ++;
        } while (i != cycleStart);
    }
}

distance = distance % size: 获取旋转的位置
使用for和do-while循环，每次循环都将一个元素放到目标位置，在do-while中判断 i != cycleStart，直到所有元素都放置到正确的位置
最终list所有元素被循环替换完成，这个操作相当于从某个位置开始进行正序旋转的操作

rotate2:

private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid =  -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;
    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

主要针对大于100个元素的LinkedList进行操作

定位拆链位置(distance % size + size)，即我们要旋转后找到的元素位置
第一次翻转，从位置0到拆链位置
第二次翻转，从拆链位置到最后一个元素
第三次翻转，翻转整个链表

java.util.Collections工具包

Collections.sort 排序​

源码​

Collections.binarySearch 二分查找​

源码​

Collections.shuffle 洗牌算法​

源码​

Collections.rotate 旋转算法​

源码​

`Collections.sort` 排序

源码

`Collections.binarySearch` 二分查找

源码

`Collections.shuffle` 洗牌算法

源码

`Collections.rotate` 旋转算法

源码