关于数据结构和算法:面经手册-第10篇扫盲javautilCollections工具包学习排序二分洗牌旋转算法

作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！????

一、前言

算法是数据结构的灵魂！

好的算法搭配上适合的数据结构，能够让代码性能大大的晋升效率。当然，算法学习不只是刷题，还须要落地与利用，否则到了写代码的时候，还是会for 循环+ifelse。

当开发一个略微简单点的业务流程时，往往要用到与之符合的数据结构和算法逻辑，在与设计模式联合，这样既能让你的写出具备高性能的代码，也能让这些代码具备良好的扩展性。

在以往的章节中，咱们把 Java 罕用的数据结构根本介绍完了，都已收录到：跳转 ->《面经手册》，章节内容下图；

那么，有了这些数据结构的根底，接下来咱们再学习一下 Java 中提供的算法工具类，Collections。

二、面试题

谢飞机，明天怎么垂头丧气的呢，还有黑眼圈？

答：好多常识盲区呀，最近始终在致力补短板，还有面经手册里的数据结构。

问：那数据结构看的差不多了吧，你有思考???? 过，数据结构里波及的排序、二分查找吗？

答：二分查找会一些，巴拉巴拉。

问：还不错，那你晓得这个办法在 Java 中有提供对应的工具类吗？是哪个！

答：这！？如同没留神过，没用过！

问：去吧，回家在看看书，这两天也劳动下。

飞机悄悄的出门了，但这次面试题整体答复的还是不错的，面试官决定下次再给他一个机会。

三、Collections 工具类

java.util.Collections，是 java 汇合框架的一个工具类，次要用于 Collection 提供的通用算法；排序、二分查找、洗牌等算法操作。

从数据结构到具体实现，再到算法，整体的构造如下图；

1. Collections.sort 排序

1.1 初始化汇合

List<String> list = new ArrayList<String>();
list.add("7");
list.add("4");
list.add("8");
list.add("3");
list.add("9");

1.2 默认排列[正序]

Collections.sort(list);

// 测试后果：[3, 4, 7, 8, 9]

1.3 Comparator 排序

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

• 咱们应用 o2 与 o1 做比照，这样会进去一个顺叙排序。
• 同时，Comparator还能够对对象类依照某个字段进行排序。
• 测试后果如下；

[9, 8, 7, 4, 3]

1.4 reverseOrder 倒排

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

// 测试后果：[9, 8, 7, 4, 3]

• Collections.<String>reverseOrder()的源码局部就和咱们下面把两个比照的类调换过去一样。c2.compareTo(c1);

1.5 源码简述

对于排序方面的知识点并不少，而且有点简单。本文次要介绍 Collections 汇合工具类，后续再深刻每一个排序算法进行解说。

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，而抉择 分段排序 和二分插入排序 。 这一部分内容咱们后续专门在排序内容解说

2. Collections.binarySearch 二分查找

• 看到这张图相熟吗，这就是汇合元素中通过二分查找定位指定元素 5。
• 二分查找的前提是汇合有序，否则不能满足二分算法的查找过程。

• 查找汇合元素 5，在这个汇合中分了三部；

  • 第一步，(0 + 7) >>> 1 = 3，定位 list.get(3) = 4，则持续向右侧二分查找。
  • 第二步，(4 + 7) >>> 1 = 5，定位 list.get(5) = 6，则持续向左侧二分查找。
  • 第三步，(4 + 4) >>> 1 = 4，定位 list.get(4) = 5，找到元素，返回后果。

2.1 性能应用

@Test
public void test_binarySearch() {List<String> list = new ArrayList<String>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    list.add("6");
    list.add("7");
    list.add("8");
    
    int idx = Collections.binarySearch(list, "5");
    System.out.println("二分查找：" + idx);
}

• 此性能就是上图中的具体实现成果，通过 Collections.binarySearch 定位元素。
• 测试后果：二分查找：4

2.2 源码剖析

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 进行查找。那么这里其实应用 LinkedList 存储数据，在元素定位的时候，须要 get 循环获取元素，就会比 ArrayList 更耗时。

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)，这在咱们剖析数据结构时曾经讲过。《LinkedList 插入速度比 ArrayList 快？你确定吗？》

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 的形式进行二分查找操作。也算是一个优化，然而对于链表的数据结构，依然没有数组数据结构，二分解决的速度快，次要在获取元素的工夫复杂度上 O(1) 和 O(n)。

3. Collections.shuffle 洗牌算法

洗牌算法，其实就是将 List 汇合中的元素进行打乱，个别能够用在抽奖、摇号、洗牌等各个场景中。

3.1 性能应用

Collections.shuffle(list);

Collections.shuffle(list, new Random(100));

它的应用形式非常简单，次要有这么两种形式，一种间接传入汇合、另外一种还能够传入固定的随机种子 这种形式能够管制洗牌范畴范畴

3.2 源码剖析

依照洗牌的逻辑，咱们来实现下具体的外围逻辑代码，如下；

@Test
public void test_shuffle() {List<String> list = new ArrayList<String>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    list.add("6");
    list.add("7");
    list.add("8");
    
    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)));        // 元素置换
    }
    System.out.println(list);
}

运行后果：

ri：6 ji：7
ri：4 ji：6
ri：1 ji：5
ri：2 ji：4
ri：0 ji：3
ri：0 ji：2
ri：1 ji：1
[8, 6, 4, 1, 3, 2, 5, 7]

这部分代码逻辑次要是通过随机数从逐渐放大范畴的汇合中找到对应的元素，与递加的下标地位进行元素替换，整体的执行过程如下；

4. Collections.rotate 旋转算法

旋转算法，能够把 ArrayList 或者 Linkedlist，从指定的某个地位开始，进行正旋或者逆旋操作。有点像把汇合了解成圆盘，把要的元素转到本人这，其余的元素程序追随。

4.1 性能利用

List<String> list = new ArrayList<String>();
list.add("7");
list.add("4");
list.add("8");
list.add("3");
list.add("9");
Collections.rotate(list, 2);
System.out.println(list);

这里咱们将汇合程序；7、4、8、3、9，顺时针旋转 2 位，测试后果如下；逆时针旋转为正数

测试后果

[3, 9, 7, 4, 8]

通过测试后果咱们能够看到，从元素 7 开始，正向旋转了两位，执行成果如下图；

4.2 源码剖析

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

对于旋转算法的实现类分为两局部；

1. Arraylist 或者元素数量不多时，ROTATE_THRESHOLD = 100，则通过算法 rotate1 实现。
2. 如果是 LinkedList 元素数量又超过了 ROTATE_THRESHOLD，则须要应用算法 rotate2 实现。

那么，这两个算法有什么不同呢？

4.2.1 旋转算法，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);
    }
}

这部分代码看着略微多一点，然而数组构造的操作起来并不简单，根本如下面圆圈图操作，次要包含以下步骤；

1. distance = distance % size;，获取旋转的地位。
2. for 循环和 dowhile，配合每次的旋转操作，比方这里第一次会把 0 地位元素替换到 2 地位，接着在 dowhile 中会判断i != cycleStart，满足条件持续把替换了 2 地位的元素持续往下替换。直到一轮循环把所有元素都搁置到正确地位。
3. 最终 list 元素被循环替换实现，也就相当从某个地位开始，正序旋转 2 个地位的操作。

4.2.2 旋转算法，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 进行操作，所以整个算法也更加有意思，它的次要操作包含；

1. 定位拆链地位，-distance % size + size，也就是咱们要旋转后找到的元素地位
2. 第一次翻转，把从地位 0 到拆链地位
3. 第二次翻转，把拆链地位到结尾
4. 第三次翻转，翻转整个链表

整体执行过程，能够参考下图，更不便了解；

5. 其余 API 介绍

这部分 API 内容，应用和设计上绝对比较简单，平时可能用的时候不多，但有的小伙伴还没用过，就当为你扫盲了。

5.1 最大最小值

String min = Collections.min(Arrays.asList("1", "2", "3"));
String max = Collections.max(Arrays.asList("1", "2", "3"));

• Collections 工具包能够进行最值的获取。

5.2 元素替换

 List<String> list = new ArrayList<String>();
 list.add("7");
 list.add("4");
 list.add("8");
 list.add("8");
 Collections.replaceAll(list, "8", "9");
 
 // 测试后果：[7, 4, 9, 9]

• 能够把汇合中某个元素全副替换成新的元素。

5.3 间断汇合地位判断

@Test
public void test_indexOfSubList() {List<String> list = new ArrayList<String>();
    list.add("7");
    list.add("4");
    list.add("8");
    list.add("3");
    list.add("9");
    int idx = Collections.indexOfSubList(list, Arrays.asList("8", "3"));
    System.out.println(idx);
    
    // 测试后果：2
}

在应用 String 操作中，咱们晓得 "74839".indexOf("8");，能够获取某个元素在什么地位。而在ArrayList 汇合操作中，能够获取间断的元素，在汇合中的地位。

5.4 synchronized

List<String> list = Collections.synchronizedList(new ArrayList<String>());
Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());

• 这个很相熟吧，甚至常常应用，但可能会疏忽这些线程平安的办法来自于 Collections 汇合工具包。

四、总结

• 本章节根本将 java.util.Collections 工具包中的罕用办法介绍完了，以及一些算法的解说。这样在后续须要应用到这些算法逻辑时，就能够间接应用并不需要反复造轮子。
• 学习数据结构、算法、设计模式，这三方面的常识，重点还是能落地到日常的业务开发中，否则空、假、虚，只能适宜吹吹牛，并不会给我的项目研发带来理论的价值。
• 懂了就是真的懂，别让本人太难受。死记硬背谁也受不了，消耗了大量的工夫，常识也没有排汇，学习一个知识点最好就从基本学习，不要心浮气躁。

五、系列举荐

• DDD 畛域驱动设计落地计划
• 重学 Java 设计模式(22 个实在开发场景)
• 面经手册(上最快的车，拿最贵的 offer)
• 字节码编程(非入侵式全链路监控实际)