用java api進行sort

　　作者 SUNJ
　　　　本節中所描述的多態算法 （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 javautil*;
　　
　　public class Sort {
　　
　　public static void main(String args[]) {
　　
　　List l = ArraysasList(args);
　　
　　Collectionssort(l);
　　
　　Systemoutprintln(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 = mvalues(erator(); ihasNext(); ) {
　　
　　List l = (List) inext();
　　
　　if (lsize() = minGroupSize)
　　
　　winnersadd(l);
　　
　　}
　　
　　// Sort permutation groups according to size
　　
　　Collectionssort(winners new Comparator() {
　　
　　public int compare(Object o Object o) {
　　
　　return ((List)o)size() ((List)o)size();
　　
　　}
　　
　　});
　　
　　// Print permutation groups
　　
　　for (Iterator i=erator(); ihasNext(); ) {
　　
　　List l = (List) inext();
　　
　　Systemoutprintln(lsize() + : + l);
　　
　　}
　　
　　　　用與 Map 課程中使用的相同的詞典運行 這個程序 並使用相同的最小排序組尺寸（）會產生下列輸出:
　　
　　% java Perm dictionarytxt
　　
　　: [apers apres asper pares parse pears prase presa rapes
　　
　　reaps spare spear]
　　
　　: [alerts alters artels estral laster ratels salter slater
　　
　　staler stelar talers]
　　
　　: [least setal slate stale steal stela taels tales teals
　　
　　tesla]
　　
　　: [estrin inerts insert inters niters nitres sinter triens
　　
　　trines]
　　
　　: [capers crapes escarp pacers parsec recaps scrape secpar
　　
　　spacer]
　　
　　: [anestri antsier nastier ratines retains retinas retsina
　　
　　stainer stearin]
　　
　　: [palest palets pastel petals plates pleats septal staple
　　
　　tepals]
　　
　　: [carets cartes caster caters crates reacts recast traces]
　　
　　: [ates east eats etas sate seat seta teas]
　　
　　: [arles earls lares laser lears rales reals seral]
　　
　　: [lapse leaps pales peals pleas salep sepal spale]
　　
　　: [aspers parses passer prases repass spares sparse spears]
　　
　　: [earings erasing gainers reagins regains reginas searing
　　
　　seringa]
　　
　　: [enters nester renest rentes resent tenser ternes treens]
　　
　　: [peris piers pries prise ripes speir spier spire]
　　
　　&#;上一頁 下一頁&#;
　　
　　a
　　
　　混排（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) ) 這裡的 insertion point 被定義為一個點從這個點該值將被插入到這個 List 中大於該值的第一個元素的位置索引或listsize() 選用這個不可否認的難看的公式是為了保證如果且僅如果搜索鍵被發現則返回值將等於它基本上是一個將布爾邏輯 (found) 和整數 (index) 綜合到單一的int返回值的大雜燴
　　
　　　　下列慣用程序對 binarySearch 操作的兩種形式均適用它尋找特定搜索鍵如果搜索鍵不出現則將它插入到適當的位置:
　　
　　int pos = CollectionsbinarySearch(l key);
　　
　　if (pos < 0)
　　
　　l.add(-pos-1, key);
　　
　　　　尋找極值（Finding Extreme Values）
　　
　　　　min 和 max 算法分別返回包含在特定 Collection 中的最小和最大元素。Tw.wiNGWit.Com這兩個操作都各有兩種形式，簡單形式只采用一個 Collection, 並按照元素的自然排序返回最小 (或最大) 元素；另一種形式除采用 Collection 之外，還采用一個 Comparator，並按照特定 Comparator返回最小（或最大）元素。
　　
　　　　這些就是由Java 平台提供的作用於與 List 對象相對的任意 Collection 對象上的僅有算法，就象上面提到的 fill 算法一樣，這些算法都是非常簡單明了的，它們是Java平台為程序員特別提供的便利工具。
　　
　　
　　

From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19791.html