Java之道/陣列物件
牌組
deck array!of Cards
在上一章中，我們使用了物件陣列，但我也提到可以有一個物件，它包含一個數組作為例項變數。在本節中，我將建立一個新的物件，稱為 Deck，它包含一個 Card 陣列作為例項變數。
instance variable variable!instance
類定義如下所示
verbatim class Deck
Card[] cards;
public Deck (int n) cards = new Card[n];
verbatim
例項變數的名稱是 cards，以幫助區分 Deck 物件和它包含的 Card 陣列。以下是一個狀態圖，顯示了沒有分配任何卡片的 Deck 物件的樣子
state diagram constructor
figure=figs/deckobject.eps
與往常一樣，建構函式初始化例項變數，但在這種情況下，它使用 new 命令建立卡片陣列。但是，它沒有建立任何卡片來放入其中。為此，我們可以編寫另一個建構函式，它建立一個標準的 52 張牌牌組並用 Card 物件填充它
verbatim
public Deck ()
cards = new Card[52];
int index = 0;
for (int suit = 0; suit <= 3; suit++)
for (int rank = 1; rank <= 13; rank++)
cards[index] = new Card (suit, rank);
index++;
verbatim
注意此方法與 buildDeck 的相似之處，只是我們必須更改語法以使其成為建構函式。為了呼叫它，我們使用 new 命令
new statement!new
verbatim
Deck deck = new Deck ();
verbatim
現在我們有了 Deck 類，將所有與 Deck 相關的函式放入 Deck 類定義中是有意義的。檢視我們到目前為止編寫的函式，printDeck（printdeck 部分）是一個明顯的候選函式。以下是它的重寫版本，以便與 Deck 物件一起使用
printDeck
verbatim
public static void printDeck (Deck deck)
for (int i=0; i<deck.cards.length; i++)
Card.printCard (deck.cards[i]);
verbatim
我們必須更改的最明顯的事情是引數的型別，從 Card[] 到 Deck。第二個更改是我們不能再使用 deck.length 來獲取陣列的長度，因為 deck 現在是一個 Deck 物件，而不是一個數組。它包含一個數組，但它本身不是一個數組。因此，我們必須編寫 deck.cards.length 來從 Deck 物件中提取陣列並獲取陣列的長度。
出於相同的原因，我們必須使用 deck.cards[i] 來訪問陣列中的元素，而不是僅僅使用 deck[i]。最後一個更改是 printCard 的呼叫必須明確地說 printCard 在 Card 類中定義。
對於其他一些函式，不清楚它們應該包含在 Card 類還是 Deck 類中。例如，findCard 接受一個 Card 和一個 Deck 作為引數；你可以合理地將它放在任一類中。作為練習，將 findCard 移入 Deck 類並將其重寫，以便第一個引數是 Deck 物件而不是 Card 陣列。
shuffle
shuffling
對於大多數紙牌遊戲，你需要能夠洗牌；也就是說，將卡片按隨機順序排列。在隨機部分，我們看到了如何生成隨機數，但如何使用它們來洗牌並不明顯。
一種可能性是模擬人類洗牌的方式，通常是將牌組分成兩部分，然後透過交替從每個牌組中選擇來重新組裝牌組。由於人類通常不會完美洗牌，因此經過大約 7 次迭代後，牌組的順序就會很好地隨機化。但是，計算機程式會讓人討厭地每次都進行完美的洗牌，這實際上並不太隨機。事實上，經過 8 次完美的洗牌，你會發現牌組回到了你開始時的順序。有關此斷言的討論，請參閱http://www.wiskit.com/marilyn/craig.html或使用關鍵字“perfect shuffle”進行網路搜尋。
更好的洗牌演算法是遍歷牌組中的每一張卡片，並在每次迭代中選擇兩張卡片並交換它們。
pseudocode
以下是此演算法的工作原理概述。為了繪製程式草圖，我使用的是 Java 語句和英語單詞的組合，有時被稱為虛擬碼
verbatim
for (int i=0; i<deck.cards.length; i++)
// choose a random number between i and deck.cards.length
// swap the ith card and the randomly-chosen card
verbatim
使用虛擬碼的好處是，它通常可以清楚地說明你需要哪些函式。在本例中，我們需要類似於 randomInt 的東西，它在引數 low 和 high 之間選擇一個隨機整數，以及 swapCards，它接受兩個索引並交換指定位置的卡片。
random number
透過檢視隨機部分，你可能可以弄清楚如何編寫 randomInt，儘管你必須注意可能生成超出範圍的索引。
swapCards reference
你也可以自己弄清楚 swapCards。唯一棘手的部分是決定是否僅交換對卡片的引用或交換卡片的內容。選擇哪一個重要嗎？哪一個更快？
我將把這些函式的剩餘實現留給讀者作為練習。
sorting
sorting
現在我們已經把牌組弄亂了，我們需要一種方法來將其恢復到順序。具有諷刺意味的是，有一個排序演算法非常類似於洗牌演算法。此演算法有時被稱為選擇排序，因為它透過重複遍歷陣列並在每次遍歷時選擇最小的剩餘卡片來工作。
selection sort
在第一次迭代期間，我們找到最小的卡片並將其與第 0 個位置的卡片交換。在第 i 次迭代期間，我們找到第 i 個卡片右側最小的卡片並將其與第 i 個卡片交換。
以下是選擇排序的虛擬碼
verbatim
for (int i=0; i<deck.cards.length; i++)
// find the lowest card at or to the right of i
// swap the ith card and the lowest card
verbatim
同樣，虛擬碼有助於輔助函式的設計。在本例中，我們可以再次使用 swapCards，因此我們只需要一個新的函式，稱為 findLowestCard，它接受一個卡片陣列和一個它應該開始查詢的索引。
helper method method!helper
再一次，我將把實現留給讀者。
subdeck
我們應該如何表示手牌或牌組的其他子集？一個不錯的選擇是建立一個少於 52 張牌的 Deck 物件。
我們可能需要一個函式 subdeck，它接受一個卡片陣列和一個索引範圍，並返回一個包含指定牌組子集的新卡片陣列
verbatim
public static Deck subdeck (Deck deck, int low, int high) Deck sub = new Deck (high-low+1);
for (int i = 0; i<sub.cards.length; i++)
sub.cards[i] = deck.cards[low+i];
return sub;
verbatim
子牌組的長度是 high-low+1，因為 low 卡片和 high 卡片都包含在內。這種計算可能很混亂，並會導致“差一”錯誤。繪製圖片通常是避免它們的最佳方法。
constructor overloading
因為我們在 new 命令中提供了一個引數，所以將呼叫第一個建構函式，它只分配陣列，而不分配任何卡片。在 for 迴圈內部，子牌組將用來自牌組的引用的副本填充。
以下是使用 low=3 和 high=7 建立子牌組的狀態圖。結果是一手擁有 5 張與原始牌組共享的牌；也就是說，它們是別名。
figure=figs/subdeck.eps
aliasing reference
我建議別名通常不是一個好主意，因為一個子牌組中的更改將反映在其他子牌組中，這與你對真實卡片和牌組的預期行為不符。但是，如果要處理的物件是不可變的，那麼別名可能是一個合理的選擇。在本例中，可能沒有理由更改卡片的等級或花色。相反，我們將建立每個卡片一次，然後將其視為不可變物件。因此，對於 Cards 而言，別名是一個合理的選擇。
作為練習，編寫一個 findBisect 的版本，它接受一個子牌組作為引數，而不是一個牌組和一個索引範圍。哪個版本更容易出錯？你認為哪個版本更高效？
shuffling dealing
在洗牌部分，我編寫了洗牌演算法的虛擬碼。假設我們有一個名為 shuffleDeck 的函式，它接受一個牌組作為引數並對其進行洗牌，我們可以建立並洗牌一個牌組
verbatim
Deck deck = new Deck (); shuffleDeck (deck);
verbatim
然後，要發幾手牌，我們可以使用 subdeck
verbatim
Deck hand1 = subdeck (deck, 0, 4); Deck hand2 = subdeck (deck, 5, 9); Deck pack = subdeck (deck, 10, 51);
verbatim
此程式碼將前 5 張牌放在一手牌中，接下來的 5 張牌放在另一手牌中，其餘的放在牌堆中。
當你想到發牌時，你是否認為我們應該以真實紙牌遊戲中常見的輪流方式一次發一張牌給每個玩家？我考慮過這個問題，但隨後意識到對於計算機程式來說，這樣做是沒必要的。輪流約定旨在減輕不完美的洗牌，並使莊家更難作弊。這兩者對於計算機來說都不是問題。
此示例是工程隱喻的危險之一的有用提醒：有時我們對計算機施加了不必要的限制，或者期望計算機擁有它所缺乏的功能，因為我們無意中將隱喻擴充套件到了其崩潰點。當心誤導性的類比。
mergesort
efficiency sorting mergesort
在排序部分，我們看到了一種簡單的排序演算法，事實證明它效率不高。為了對專案進行排序，它必須遍歷陣列 次，每次遍歷花費的時間與 成正比。因此，總時間與 成正比。
在本節中，我將概述一種更有效的演算法，稱為歸併排序。為了對專案進行排序，歸併排序花費的時間與 成正比。這可能看起來並不令人印象深刻，但是隨著 的增大， 和 之間的差異可能會變得巨大。嘗試幾個 的值並看看。
歸併排序背後的基本思想是：如果你有兩個子牌組，每個子牌組都已排序，那麼將它們合併成一個排序的牌組很容易（而且很快）。嘗試用一副牌試試
enumerate
將一副牌分成兩副，每副大約 10 張牌。 將它們排序，使得牌面朝上時，最小牌在最上面。 將兩副牌面朝上地放在你的面前。
比較兩副牌頂端的牌，選擇較小的牌。 翻轉它並將其新增到合併後的牌堆中。
重複步驟 2，直到其中一副牌為空。 然後，將剩餘的牌新增到合併後的牌堆中。
enumerate
最終結果應該是一副排序好的牌。 下面是虛擬碼示例：
verbatim
public static Deck merge (Deck d1, Deck d2) // create a new deck big enough for all the cards Deck result = new Deck (d1.cards.length + d2.cards.length);
// use the index i to keep track of where we are in // the first deck, and the index j for the second deck int i = 0; int j = 0;
// the index k traverses the result deck for (int k = 0; k<result.cards.length; k++)
// if d1 is empty, d2 wins; if d2 is empty, d1 wins;
// otherwise, compare the two cards
// add the winner to the new deck return result;
verbatim
測試合併演算法的最佳方法是：構建一副牌並洗牌，使用 `subdeck` 方法建立兩副（小）牌，然後使用上一章的排序例程對兩副牌進行排序。 然後，將這兩副牌傳遞給 `merge` 函式，以檢視它是否正常工作。
testing
如果能夠使其正常工作，請嘗試實現一個簡單的 `mergeSort` 函式。
verbatim
public static Deck mergeSort (Deck deck) // find the midpoint of the deck // divide the deck into two subdecks // sort the subdecks using sortDeck // merge the two halves and return the result
verbatim
然後，如果它也能正常工作，真正的樂趣就開始了！合併排序演算法的神奇之處在於它是一種遞迴演算法。 當你對子牌堆進行排序時，為什麼使用舊的、速度慢的排序演算法？ 為什麼不用你正在編寫的新的 `mergeSort` 演算法呢？
recursion
這不僅是一個好主意，也是為了獲得我承諾的效能優勢所必需的。 但是，為了使其工作，你必須新增一個基本情況，以防止它無限遞迴。 一個簡單的情況是包含 0 或 1 張牌的子牌堆。 如果 `mergeSort` 收到這樣的小牌堆，它可以直接返回，因為它們已經排序。
遞迴版本的 `mergeSort` 應該類似於：
verbatim
public static Deck mergeSort (Deck deck) // if the deck is 0 or 1 cards, return it
// find the midpoint of the deck // divide the deck into two subdecks // sort the subdecks using mergesort // merge the two halves and return the result
verbatim
像往常一樣，思考遞迴程式有兩種方式：你可以思考整個執行流程，或者你可以跳過“信任的跳躍”。 為了鼓勵你進行信任的跳躍，我故意構建了這個示例。
leap of faith
當使用 `sortDeck` 函式對子牌堆進行排序時，你並沒有強迫自己遵循執行流程，對吧？ 你只是假設 `sortDeck` 方法會正常工作，因為你已經除錯過了。 好吧，為了讓 `mergeSort` 成為遞迴函式，你所做的只是用另一種排序演算法替換了一個。 沒有理由用不同的方式閱讀程式。
好吧，實際上你需要考慮正確地獲取基本情況，並確保最終能到達它，除此之外，編寫遞迴版本應該沒有問題。 祝你好運！
術語表
[edit | edit source]描述
[虛擬碼：] 一種透過使用英語和 Java 程式碼的組合編寫程式草稿的方法。
[輔助方法：] 通常是一個小方法，它本身並不做任何特別有用的事情，但它可以幫助另一個更有用的方法。
pseudocode helper method method!helper
描述