數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版）課件 第12章 常用算法與Collections類

第12章常用算法與Collections類2024/11/912024/11/922024/11/93Collections類是Object類的一個(gè)直接子類（注意Collections比Collection多了一個(gè)字母s），該類封裝了一系列算法，例如，二分查找，排序、洗牌等算法，這些算法可用于List，Queue、Set。需要注意的是Collections是類，Collection是接口，Collections類沒有實(shí)現(xiàn)Collection接口.12.1排序2024/11/94

2024/11/9512.1排序例子1Score.java例子1中的主類Example12_1使用Collections類的sort()方法排序（升序）一個(gè)鏈表，首先按鏈表中的對象實(shí)現(xiàn)的Comparable接口給出的比較器排序鏈表，然后再指定新的比較器排序鏈表。Example12_1.java12.2二分查找2024/11/96publicstaticintbinarySearch(List<?extendsT>list,Tkey)查找對象key是否在升序的list中（list中的對象按自然序排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開始），否則返回一個(gè)負(fù)數(shù)。publicstaticintbinarySearch(List<?extendsT>list,Tkey,Comparator<?superT>c)查找對象key是否在升序的list中（list的元素按比較器c排序），如果key在list中，方法返回key在list中的索引位置（索引位置從0開始），否則返回一個(gè)負(fù)數(shù)。注意，排序使用的比較器的算法需要和該方法使用的比較器c的算法相同。2024/11/9712.2二分查找例子2FindWords.java例子2中的FindWords類的booleanfindWords(Stringstr,Stringkey)方法使用二分法判斷單詞key是否在str中。Example12_2.java12.3反轉(zhuǎn)與旋轉(zhuǎn)2024/11/98publicstaticvoidreverse(List<?>list)反轉(zhuǎn)list中元素的順序.publicstaticvoidrotate(List<?>list,intdistance)把list向右(distance是正整數(shù))或向左(distance是負(fù)整數(shù))旋轉(zhuǎn)distance個(gè)索引位置。例如，list節(jié)點(diǎn)中的對象依次是[a,b,c,d,e]，如果執(zhí)行Colections.rotate(list,1)，那么list節(jié)點(diǎn)中的對象依次是[e,a,b,c,d]，如果執(zhí)行Colections.rotate(list,-2)，那么list節(jié)點(diǎn)中的對象依次是[cdeab]。2024/11/9912.3反轉(zhuǎn)與旋轉(zhuǎn)例子3LeaveOne.javaWordReverse.java例子3中的LeaveOne類的leaveByRotate(LinkedList<Integer>list)方法通過旋轉(zhuǎn)鏈表，解決約瑟夫問題：把list向左旋轉(zhuǎn)2個(gè)索引位置，即可確定出退出圈中的人，理由是，此刻鏈表頭節(jié)點(diǎn)就是數(shù)到的第3個(gè)人，即要出圈的人。例子3的WordRevers類的isReverse(Stringword)方法判斷word是否是回文單詞（回文單詞和它的反轉(zhuǎn)相同）。建議讀者把這里的例子3和第4章的例子9做一個(gè)比較，體會(huì)使用旋轉(zhuǎn)list解決約瑟夫問題，能讓代碼更加簡練。Example12_3.java12.4洗牌2024/11/910我們曾在第4章的4.10節(jié)，講解過洗牌算法，即Fisher-Yates洗牌算法。Collections類將Fisher-Yates洗牌算法封裝在下列方法中：publicstaticvoidshuffle(List<?>list)使用Fisher-Yates洗牌算法排列l(wèi)ist。2024/11/91112.4洗牌例子4例子4的主類Example12_4使用Collectiones類提供的Fisher-Yates洗牌算法演示洗牌過程。Example12_4.java12.5最大與最小2024/11/912publicstaticTmax(Collection<?extendsT>coll)按coll元素的自然序（元素實(shí)現(xiàn)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相等的元素的數(shù)量。我們曾在第10章的例子5中，使用散列表統(tǒng)計(jì)文本文件中單詞出現(xiàn)的次數(shù)和頻率。下面的例子6使用intfrequency(Collection<?>c,Objectobj)方法統(tǒng)計(jì)文本文件中單詞或漢字出現(xiàn)的次數(shù)和頻率。2024/11/91512.5最大與最小例子6Example12_6.java例子6中的FrequencyEnglish類將英文組成的文本文件中的單詞存放在一個(gè)集合中，便于統(tǒng)計(jì)出不相同的單詞的總數(shù)，把單詞存放在一個(gè)鏈表中，便于統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的次數(shù)，