javaapi之算法
?font color="#FF0000">算法
本節中所描述的多態算法 （polymorphic algorithms）是由 JDK 所提供的可重復使用的功能性片段。它們均取自Collections類，并都采用靜態方法（它的第一個參數是執行操作的 對象集）的形式。由Java平臺所提供的絕大多數算法都操作于List對象，但有兩個 (min 和 max) 操作于任意Collection對象。以下是關于算法的描述
排序（Sorting）
排序算法可為一個 List 重新排序，以使它的元素按照某種排序關系成上升式排序。有兩種形式的操作被提供。簡單形式的操作只采用一個 List 并按照它的元素的自然排序進行排序。如果你對自然排序的概念不熟悉，那么應該重新閱讀 對象排序（Object Ordering）.
sort 操作使用做了些優化的合并排序（merge sort） 算法。如果你不知道它的含義，而又很看重它的話， 請閱讀關于算法的任意一種教科書。這個算法的重要之處是：
快速: 這個算法被保證運行在 n log(n) 時間內，并在已基本排序的列表上，它的速度實質上更快。經驗表明，它的速度與高度優化的快速排序（quicksort）的速度差不多， Quicksort 一般被認為快于合并排序，但它不穩定，并不保證 n log(n)性能。
穩定: 這就是說，它不為相等的元素重新排序。如果你為相同的列表做不同屬性的重復排序，這一點對你來說是十分重要的。如果一個郵件程序的用戶為它的郵件箱按日期排序，然后又按發件人排序，這個用戶自然地期望某個特定發件人的現在相鄰的消息列表將（仍然）按日期排序。這一點只有在第二個排序是穩定的時候才能得以保證。
以下是 一個小程序，它可按詞典（字母）順序打印它的參數：
import java.util.*;
public class Sort {
public static void main(String args[]) {
List l = Arrays.asList(args);
Collections.sort(l);
System.out.println(l);
}
}
讓我們運行這個程序：
% java Sort i walk the line
[i, line, the, walk]
演示這個程序只是為了表示我是毫無保留的：這個算法確實是象它們所顯現的那樣簡單。我不想低估你的能力而演示更傻的例子。
第二種形式的 sort除采用一個 List 外，還采用一個 Comparator 并且使用 Comparator 對元素進行排序。還記得在 Map 課程結 鋇吶帕兇櫚睦勇? 它以一個非特定的順序打印出排列組。假設你要以相反的大小順序打印它們，大的排列在前面。下列例子將告訴你如何借助 sort 方法的第二種形式而達到你的目的。
回想一下，排序表是以 List 對象的形式作為一個 Map 中的值而被存儲的。修改后的打印代碼通過 Map 的 values視圖進行迭代, 將每一個通過最小尺寸測試的List放進List 之中。然后，代碼使用一個期望 List 對象的 Comparator 為這個 List 排序，并實現反轉大小排序。最終，代碼通過現在已排序的 List 進行迭代，打印它的元素（排序組）。這個代碼在 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 課程中使用的相同的詞典運行 這個程序 ，并使用相同的最小排序組尺寸（8），會產生下列輸出:
% 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]
混排（Shuffling）
混排算法所做的正好與 sort 相反: 它打亂在一個 List 中可能有的任何排列的蹤跡。也就是說，基于隨機源的輸入重排該 List, 這樣的排列具有相同的可能性（假設隨機源是公正的）。這個算法在實現一個碰運氣的游戲中是非常有用的。例如，它可被用來混排代表一副牌的 Card 對象的一個 List 。另外，在生成測試案例時，它也是十分有用的。
這個操作有兩種形式。第一種只采用一個 List 并使用默認隨機源。第二種要求調用者提供一個 Random 對象作為隨機源。這個算法的一些實際代碼曾在 List 課程中被作為例子使用。
常規數據操作（Routine Data Manipulation）
Collections 類為在 List 對象上的常規數據操作提供了三種算法。這些算法是十分簡單明了的:
reverse: 反轉在一個列表中的元素的順序。
fill: 用特定值覆蓋在一個 List 中的每一個元素。這個操作對初始化一個 List 是十分有用的。
copy: 用兩個參數，一個目標 List 和一個源 List, 將源的元素拷貝到目標，并覆蓋它的內容。目標 List 至少與源一樣長。如果它更長，則在目標 List 中的剩余元素不受影響。
搜索（Searching）
binary search （二進制搜索）算法用二進制搜索算法在一個已排序的 List 中尋找特定元素。這個算法有兩種形式。第一種采用一個 List 和一個要尋找的元素 ( "搜索鍵（search key）")。這種形式假設 List 是按照它的元素的自然排序排列成上升順序的。第二種形式除采用 List 外，還采用一個 Comparator 以及搜索鍵，并假設 List 是按照特定 Comparator 排列成上升順序的。 排序算法(描述見上) 可優先于 binarySearch 而被用來為List 排序。
兩種形式的返回值是相同的: 如果 List 包含搜索鍵，它的索引將被返回；如果不包括，則返回值為 (-(insertion point) - 1), 這里的 insertion point 被定義為一個點，從這個點該值將被插入到這個 List 中：大于該值的第一個元素的位置索引，或list.size()。 選用這個不可否認的難看的公式是為了保證如果且僅如果搜索鍵被發現，則返回值將等于0。它基本上是一個將布爾邏輯 ("found") 和整數 ("index") 綜合到單一的int返回值的大雜燴。
下列慣用程序對 binarySearch 操作的兩種形式均適用，它尋找特定搜索鍵，如果搜索鍵不出現，則將它插入到適當的位置:
int pos = Collections.binarySearch(l, key);
if (pos $#@60; 0)
l.add(-pos-1, key);
尋找極值（Finding Extreme Values）
min 和 max 算法分別返回包含在特定 Collection 中的最小和最大元素。這兩個操作都各有兩種形式，簡單形式只采用一個 Collection, 并按照元素的自然排序返回最小 (或最大) 元素；另一種形式除采用 Collection 之外，還采用一個 Comparator，并按照特定 Comparator返回最小（或最大）元素。
這些就是由Java 平臺提供的作用于與 List 對象相對的任意 Collection 對象上的僅有算法，就象上面提到的 fill 算法一樣，這些算法都是非常簡單明了的，它們是Java平臺為程序員特別提供的便利工具。
本節中所描述的多態算法 （polymorphic algorithms）是由 JDK 所提供的可重復使用的功能性片段。它們均取自Collections類，并都采用靜態方法（它的第一個參數是執行操作的 對象集）的形式。由Java平臺所提供的絕大多數算法都操作于List對象，但有兩個 (min 和 max) 操作于任意Collection對象。以下是關于算法的描述
排序（Sorting）
排序算法可為一個 List 重新排序，以使它的元素按照某種排序關系成上升式排序。有兩種形式的操作被提供。簡單形式的操作只采用一個 List 并按照它的元素的自然排序進行排序。如果你對自然排序的概念不熟悉，那么應該重新閱讀 對象排序（Object Ordering）.
sort 操作使用做了些優化的合并排序（merge sort） 算法。如果你不知道它的含義，而又很看重它的話， 請閱讀關于算法的任意一種教科書。這個算法的重要之處是：
快速: 這個算法被保證運行在 n log(n) 時間內，并在已基本排序的列表上，它的速度實質上更快。經驗表明，它的速度與高度優化的快速排序（quicksort）的速度差不多， Quicksort 一般被認為快于合并排序，但它不穩定，并不保證 n log(n)性能。
穩定: 這就是說，它不為相等的元素重新排序。如果你為相同的列表做不同屬性的重復排序，這一點對你來說是十分重要的。如果一個郵件程序的用戶為它的郵件箱按日期排序，然后又按發件人排序，這個用戶自然地期望某個特定發件人的現在相鄰的消息列表將（仍然）按日期排序。這一點只有在第二個排序是穩定的時候才能得以保證。
以下是 一個小程序，它可按詞典（字母）順序打印它的參數：
import java.util.*;
public class Sort {
public static void main(String args[]) {
List l = Arrays.asList(args);
Collections.sort(l);
System.out.println(l);
}
}
讓我們運行這個程序：
% java Sort i walk the line
[i, line, the, walk]
演示這個程序只是為了表示我是毫無保留的：這個算法確實是象它們所顯現的那樣簡單。我不想低估你的能力而演示更傻的例子。
第二種形式的 sort除采用一個 List 外，還采用一個 Comparator 并且使用 Comparator 對元素進行排序。還記得在 Map 課程結 鋇吶帕兇櫚睦勇? 它以一個非特定的順序打印出排列組。假設你要以相反的大小順序打印它們，大的排列在前面。下列例子將告訴你如何借助 sort 方法的第二種形式而達到你的目的。
回想一下，排序表是以 List 對象的形式作為一個 Map 中的值而被存儲的。修改后的打印代碼通過 Map 的 values視圖進行迭代, 將每一個通過最小尺寸測試的List放進List 之中。然后，代碼使用一個期望 List 對象的 Comparator 為這個 List 排序，并實現反轉大小排序。最終，代碼通過現在已排序的 List 進行迭代，打印它的元素（排序組）。這個代碼在 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 課程中使用的相同的詞典運行 這個程序 ，并使用相同的最小排序組尺寸（8），會產生下列輸出:
% 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]
混排（Shuffling）
混排算法所做的正好與 sort 相反: 它打亂在一個 List 中可能有的任何排列的蹤跡。也就是說，基于隨機源的輸入重排該 List, 這樣的排列具有相同的可能性（假設隨機源是公正的）。這個算法在實現一個碰運氣的游戲中是非常有用的。例如，它可被用來混排代表一副牌的 Card 對象的一個 List 。另外，在生成測試案例時，它也是十分有用的。
這個操作有兩種形式。第一種只采用一個 List 并使用默認隨機源。第二種要求調用者提供一個 Random 對象作為隨機源。這個算法的一些實際代碼曾在 List 課程中被作為例子使用。
常規數據操作（Routine Data Manipulation）
Collections 類為在 List 對象上的常規數據操作提供了三種算法。這些算法是十分簡單明了的:
reverse: 反轉在一個列表中的元素的順序。
fill: 用特定值覆蓋在一個 List 中的每一個元素。這個操作對初始化一個 List 是十分有用的。
copy: 用兩個參數，一個目標 List 和一個源 List, 將源的元素拷貝到目標，并覆蓋它的內容。目標 List 至少與源一樣長。如果它更長，則在目標 List 中的剩余元素不受影響。
搜索（Searching）
binary search （二進制搜索）算法用二進制搜索算法在一個已排序的 List 中尋找特定元素。這個算法有兩種形式。第一種采用一個 List 和一個要尋找的元素 ( "搜索鍵（search key）")。這種形式假設 List 是按照它的元素的自然排序排列成上升順序的。第二種形式除采用 List 外，還采用一個 Comparator 以及搜索鍵，并假設 List 是按照特定 Comparator 排列成上升順序的。 排序算法(描述見上) 可優先于 binarySearch 而被用來為List 排序。
兩種形式的返回值是相同的: 如果 List 包含搜索鍵，它的索引將被返回；如果不包括，則返回值為 (-(insertion point) - 1), 這里的 insertion point 被定義為一個點，從這個點該值將被插入到這個 List 中：大于該值的第一個元素的位置索引，或list.size()。 選用這個不可否認的難看的公式是為了保證如果且僅如果搜索鍵被發現，則返回值將等于0。它基本上是一個將布爾邏輯 ("found") 和整數 ("index") 綜合到單一的int返回值的大雜燴。
下列慣用程序對 binarySearch 操作的兩種形式均適用，它尋找特定搜索鍵，如果搜索鍵不出現，則將它插入到適當的位置:
int pos = Collections.binarySearch(l, key);
if (pos $#@60; 0)
l.add(-pos-1, key);
尋找極值（Finding Extreme Values）
min 和 max 算法分別返回包含在特定 Collection 中的最小和最大元素。這兩個操作都各有兩種形式，簡單形式只采用一個 Collection, 并按照元素的自然排序返回最小 (或最大) 元素；另一種形式除采用 Collection 之外，還采用一個 Comparator，并按照特定 Comparator返回最小（或最大）元素。
這些就是由Java 平臺提供的作用于與 List 對象相對的任意 Collection 對象上的僅有算法，就象上面提到的 fill 算法一樣，這些算法都是非常簡單明了的，它們是Java平臺為程序員特別提供的便利工具。