数据结构与算法（Java语言版）课件 第12章 常用算法与Collections类

第12章常用算法与Collections类2024/11/912024/11/922024/11/93Collections类是Object类的一个直接子类（注意Collections比Collection多了一个字母s），该类封装了一系列算法，例如，二分查找，排序、洗牌等算法，这些算法可用于List，Queue、Set。需要注意的是Collections是类，Collection是接口，Collections类没有实现Collection接口.12.1排序2024/11/94

2024/11/9512.1排序例子1Score.java例子1中的主类Example12_1使用Collections类的sort()方法排序（升序）一个链表，首先按链表中的对象实现的Comparable接口给出的比较器排序链表，然后再指定新的比较器排序链表。Example12_1.java12.2二分查找2024/11/96publicstaticintbinarySearch(List<?extendsT>list,Tkey)查找对象key是否在升序的list中（list中的对象按自然序排序），如果key在list中，方法返回key在list中的索引位置（索引位置从0开始），否则返回一个负数。publicstaticintbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)查找对象key是否在升序的list中（list的元素按比较器c排序），如果key在list中，方法返回key在list中的索引位置（索引位置从0开始），否则返回一个负数。注意，排序使用的比较器的算法需要和该方法使用的比较器c的算法相同。2024/11/9712.2二分查找例子2FindWords.java例子2中的FindWords类的booleanfindWords(Stringstr,Stringkey)方法使用二分法判断单词key是否在str中。Example12_2.java12.3反转与旋转2024/11/98publicstaticvoidreverse(List<?>list)反转list中元素的顺序.publicstaticvoidrotate(List<?>list,intdistance)把list向右(distance是正整数)或向左(distance是负整数)旋转distance个索引位置。例如，list节点中的对象依次是[a,b,c,d,e]，如果执行Colections.rotate(list,1)，那么list节点中的对象依次是[e,a,b,c,d]，如果执行Colections.rotate(list,-2)，那么list节点中的对象依次是[cdeab]。2024/11/9912.3反转与旋转例子3LeaveOne.javaWordReverse.java例子3中的LeaveOne类的leaveByRotate(LinkedList<Integer>list)方法通过旋转链表，解决约瑟夫问题：把list向左旋转2个索引位置，即可确定出退出圈中的人，理由是，此刻链表头节点就是数到的第3个人，即要出圈的人。例子3的WordRevers类的isReverse(Stringword)方法判断word是否是回文单词（回文单词和它的反转相同）。建议读者把这里的例子3和第4章的例子9做一个比较，体会使用旋转list解决约瑟夫问题，能让代码更加简练。Example12_3.java12.4洗牌2024/11/910我们曾在第4章的4.10节，讲解过洗牌算法，即Fisher-Yates洗牌算法。Collections类将Fisher-Yates洗牌算法封装在下列方法中：publicstaticvoidshuffle(List<?>list)使用Fisher-Yates洗牌算法排列list。2024/11/91112.4洗牌例子4例子4的主类Example12_4使用Collectiones类提供的Fisher-Yates洗牌算法演示洗牌过程。Example12_4.java12.5最大与最小2024/11/912publicstaticTmax(Collection<?extendsT>coll)按coll元素的自然序（元素实现Comparable接口中的比较器给出的大小顺序），返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll)按coll元素的自然序，返回coll中的最小值。publicstaticTmax(Collection<?extendsT>coll,Comparator<?superT>comp)

按comp比较器，返回coll中的最大值。publicstaticTmin(Collection<?extendsT>coll,,Comparator<?superT>comp)按comp比较器，返回coll中的最小值。2024/11/91312.5最大与最小例子5Example12_5.java例子5中的主类Example12_5求集合中的最大值和最小值。12.6频率2024/11/914publicstaticintfrequency(Collection<?>c,Objectobj)返回c中与指定对象obj相等的元素的数量。我们曾在第10章的例子5中，使用散列表统计文本文件中单词出现的次数和频率。下面的例子6使用intfrequency(Collection<?>c,Objectobj)方法统计文本文件中单词或汉字出现的次数和频率。2024/11/91512.5最大与最小例子6Example12_6.java例子6中的FrequencyEnglish类将英文组成的文本文件中的单词存放在一个集合中，便于统计出不相同的单词的总数，把单词存放在一个链表中，便于统计每个单词出现的次数，