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 排列成上升順序的。 排序算法(描述見(jiàn)上) 可優(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)為程序員特別提供的便利工具。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的java 排序api_用java api进行sort的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。