java api之算法

2019-11-18 15:39:52

字體：大中小

來源：轉載

供稿：網友

　　?算法

　　本節中所描述的多態算法（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)

上一篇：虛擬現實之高級技巧（五）

下一篇：J2ME 2D小游戲入門之周邊工具類