Sun授權(quán)刊登
本節(jié)中所描述的多態(tài)算法 （polymorphic algorithms）是由 JDK 所提供的可重復(fù)使用的功能性片段。它們均取自Collections類，并都采用靜態(tài)方法（它的第一個(gè)參數(shù)是執(zhí)行操作的 對(duì)象集）的形式。由Java平臺(tái)所提供的絕大多數(shù)算法都操作于List對(duì)象，但有兩個(gè) (min 和 max) 操作于任意Collection對(duì)象。以下是關(guān)于算法的描述
排序（Sorting）
排序算法可為一個(gè) List 重新排序，以使它的元素按照某種排序關(guān)系成上升式排序。有兩種形式的操作被提供。簡(jiǎn)單形式的操作只采用一個(gè) List 并按照它的元素的自然排序進(jìn)行排序。如果你對(duì)自然排序的概念不熟悉，那么應(yīng)該重新閱讀 對(duì)象排序（Object Ordering）.
sort 操作使用做了些優(yōu)化的合并排序（merge sort） 算法。如果你不知道它的含義，而又很看重它的話， 請(qǐng)閱讀關(guān)于算法的任意一種教科書。這個(gè)算法的重要之處是：
快速: 這個(gè)算法被保證運(yùn)行在 n log(n) 時(shí)間內(nèi)，并在已基本排序的列表上，它的速度實(shí)質(zhì)上更快。經(jīng)驗(yàn)表明，它的速度與高度優(yōu)化的快速排序（quicksort）的速度差不多， Quicksort 一般被認(rèn)為快于合并排序，但它不穩(wěn)定，并不保證 n log(n)性能。
穩(wěn)定: 這就是說(shuō)，它不為相等的元素重新排序。如果你為相同的列表做不同屬性的重復(fù)排序，這一點(diǎn)對(duì)你來(lái)說(shuō)是十分重要的。如果一個(gè)郵件程序的用戶為它的郵件箱按日期排序，然后又按發(fā)件人排序，這個(gè)用戶自然地期望某個(gè)特定發(fā)件人的現(xiàn)在相鄰的消息列表將（仍然）按日期排序。這一點(diǎn)只有在第二個(gè)排序是穩(wěn)定的時(shí)候才能得以保證。
以下是 一個(gè)小程序，它可按詞典（字母）順序打印它的參數(shù)：
import java.util.*;
public class Sort {
public static void main(String args[]) {
List l = Arrays.asList(args);
Collections.sort(l);
System.out.println(l);
}
}
讓我們運(yùn)行這個(gè)程序：
% java Sort i walk the line
[i, line, the, walk]
演示這個(gè)程序只是為了表示我是毫無(wú)保留的：這個(gè)算法確實(shí)是象它們所顯現(xiàn)的那樣簡(jiǎn)單。我不想低估你的能力而演示更傻的例子。
第二種形式的 sort除采用一個(gè) List 外，還采用一個(gè) Comparator 并且使用 Comparator 對(duì)元素進(jìn)行排序。還記得在 Map 課程結(jié)束時(shí)的排列組的例子嗎? 它以一個(gè)非特定的順序打印出排列組。假設(shè)你要以相反的大小順序打印它們，大的排列在前面。下列例子將告訴你如何借助 sort 方法的第二種形式而達(dá)到你的目的。
回想一下，排序表是以 List 對(duì)象的形式作為一個(gè) Map 中的值而被存儲(chǔ)的。修改后的打印代碼通過(guò) Map 的 values視圖進(jìn)行迭代, 將每一個(gè)通過(guò)最小尺寸測(cè)試的List放進(jìn)List 之中。然后，代碼使用一個(gè)期望 List 對(duì)象的 Comparator 為這個(gè) List 排序，并實(shí)現(xiàn)反轉(zhuǎn)大小排序。最終，代碼通過(guò)現(xiàn)在已排序的 List 進(jìn)行迭代，打印它的元素（排序組）。這個(gè)代碼在 Perm 的 main 方法末尾替代了打印代碼:
// Make a List of all permutation groups above size threshold
List winners = new ArrayList();
for (Iterator i = m.values().iterator(); i.hasNext(); ) {
List l = (List) i.next();
if (l.size() = minGroupSize)
winners.add(l);
}
// Sort permutation groups according to size
Collections.sort(winners, new Comparator() {
public int compare(Object o1, Object o2) {
return ((List)o2).size() - ((List)o1).size();
}
});
// Print permutation groups
for (Iterator i=winners.iterator(); i.hasNext(); ) {
List l = (List) i.next();
System.out.println(l.size() + ": " + l);
}
用與 Map 課程中使用的相同的詞典運(yùn)行 這個(gè)程序 ，并使用相同的最小排序組尺寸（8），會(huì)產(chǎn)生下列輸出:
% java Perm dictionary.txt 8
12: [apers, apres, asper, pares, parse, pears, prase, presa, rapes,
reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter, slater,
staler, stelar, talers]
10: [least, setal, slate, stale, steal, stela, taels, tales, teals,
tesla]
9: [estrin, inerts, insert, inters, niters, nitres, sinter, triens,
trines]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape, secpar,
spacer]
9: [anestri, antsier, nastier, ratines, retains, retinas, retsina,
stainer, stearin]
9: [palest, palets, pastel, petals, plates, pleats, septal, staple,
tepals]
8: [carets, cartes, caster, caters, crates, reacts, recast, traces]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse, spears]
8: [earings, erasing, gainers, reagins, regains, reginas, searing,
seringa]
8: [enters, nester, renest, rentes, resent, tenser, ternes, treens]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
上一頁(yè) 1 2 3 下一頁(yè)
a
混排（Shuffling）
混排算法所做的正好與 sort 相反: 它打亂在一個(gè) List 中可能有的任何排列的蹤跡。也就是說(shuō)，基于隨機(jī)源的輸入重排該 List, 這樣的排列具有相同的可能性（假設(shè)隨機(jī)源是公正的）。這個(gè)算法在實(shí)現(xiàn)一個(gè)碰運(yùn)氣的游戲中是非常有用的。例如，它可被用來(lái)混排代表一副牌的 Card 對(duì)象的一個(gè) List 。另外，在生成測(cè)試案例時(shí)，它也是十分有用的。
這個(gè)操作有兩種形式。第一種只采用一個(gè) List 并使用默認(rèn)隨機(jī)源。第二種要求調(diào)用者提供一個(gè) Random 對(duì)象作為隨機(jī)源。這個(gè)算法的一些實(shí)際代碼曾在 List 課程中被作為例子使用。
常規(guī)數(shù)據(jù)操作（Routine Data Manipulation）
Collections 類為在 List 對(duì)象上的常規(guī)數(shù)據(jù)操作提供了三種算法。這些算法是十分簡(jiǎn)單明了的:
reverse: 反轉(zhuǎn)在一個(gè)列表中的元素的順序。
fill: 用特定值覆蓋在一個(gè) List 中的每一個(gè)元素。這個(gè)操作對(duì)初始化一個(gè) List 是十分有用的。
copy: 用兩個(gè)參數(shù)，一個(gè)目標(biāo) List 和一個(gè)源 List, 將源的元素拷貝到目標(biāo)，并覆蓋它的內(nèi)容。目標(biāo) List 至少與源一樣長(zhǎng)。如果它更長(zhǎng)，則在目標(biāo) List 中的剩余元素不受影響。
搜索（Searching）
binary search （二進(jìn)制搜索）算法用二進(jìn)制搜索算法在一個(gè)已排序的 List 中尋找特定元素。這個(gè)算法有兩種形式。第一種采用一個(gè) List 和一個(gè)要尋找的元素 ( "搜索鍵（search key）")。這種形式假設(shè) List 是按照它的元素的自然排序排列成上升順序的。第二種形式除采用 List 外，還采用一個(gè) Comparator 以及搜索鍵，并假設(shè) List 是按照特定 Comparator 排列成上升順序的。 排序算法(描述見上) 可優(yōu)先于 binarySearch 而被用來(lái)為L(zhǎng)ist 排序。
兩種形式的返回值是相同的: 如果 List 包含搜索鍵，它的索引將被返回；如果不包括，則返回值為 (-(insertion point) - 1), 這里的 insertion point 被定義為一個(gè)點(diǎn)，從這個(gè)點(diǎn)該值將被插入到這個(gè) List 中：大于該值的第一個(gè)元素的位置索引，或list.size()。 選用這個(gè)不可否認(rèn)的難看的公式是為了保證如果且僅如果搜索鍵被發(fā)現(xiàn)，則返回值將等于0。它基本上是一個(gè)將布爾邏輯 ("found") 和整數(shù) ("index") 綜合到單一的int返回值的大雜燴。
下列慣用程序?qū)?binarySearch 操作的兩種形式均適用，它尋找特定搜索鍵，如果搜索鍵不出現(xiàn)，則將它插入到適當(dāng)?shù)奈恢?
int pos = Collections.binarySearch(l, key);
if (pos < 0)
l.add(-pos-1, key);
尋找極值（Finding Extreme Values）
min 和 max 算法分別返回包含在特定 Collection 中的最小和最大元素。這兩個(gè)操作都各有兩種形式，簡(jiǎn)單形式只采用一個(gè) Collection, 并按照元素的自然排序返回最小 (或最大) 元素；另一種形式除采用 Collection 之外，還采用一個(gè) Comparator，并按照特定 Comparator返回最小（或最大）元素。
這些就是由Java 平臺(tái)提供的作用于與 List 對(duì)象相對(duì)的任意 Collection 對(duì)象上的僅有算法，就象上面提到的 fill 算法一樣，這些算法都是非常簡(jiǎn)單明了的，它們是Java平臺(tái)為程序員特別提供的便利工具。 |