K t qu ta s đ
c m t ph n bài chung đ
c x p đúng. Sau đây là cách làm b ng gi mã:
ế
ả
ẽ ượ
ộ
ầ
ượ ế
ằ
ả
public static
Deck merge(Deck d1, Deck d2) {
// tạo nên một cỗ bài đủ lớn chứa hết các quân bài
Deck result =
new
Deck(d1.cards.length + d2.cards.length);
// dùng chỉ số i để theo dõi vị trí hiện tại trên
// phần bài thứ nhất, và chỉ số j cho phần bài thứ hai
int
i = 0;
int
j = 0;
// chỉ số k duyệt theo phần bài được xếp đúng
for
(
int
k = 0; k < result.cards.length; k++) {
// nếu d1 rỗng thì d2 thắng; nếu d2 rỗng, d1 thắng;
// nếu không, đi so sánh hai lá bài
// thêm lá bài thắng vào phần bài được xếp đúng
}
return
result;
}
Cách hay nh t đ ki m tra
ấ ể ể
merge là l p nên và tr n m t c bài, dùng ph
ng th c subdeck đ hình
ậ
ộ
ộ ỗ
ươ
ứ
ể
thành nên hai ph n bài (nh ), r i dùng th t c sort t ch
ng tr
c đ s p x p hai n a. Sau đó b n có
ầ
ỏ ồ
ủ ụ
ừ ươ
ướ ể ắ
ế
ử
ạ
th truy n hai n a này vào
ể
ề
ử
merge đ xem ph
ng th c m i này có ho t đ ng không.
ể
ươ
ứ
ớ
ạ ộ
N u b n có th làm cho m i th nh trên ho t đ ng đ
c, hãy th m t phiên b n
ế
ạ
ể
ọ
ứ
ư
ạ ộ
ượ
ử ộ
ả mergeSort đ n gi n:
ơ
ả
public static
Deck mergeSort(Deck deck) {
// tìm điểm giữa của cỗ bài
// chia cỗ bài thành hai phần nhỏ
// xếp phần nhỏ bằng sortDeck
// trộn hai nửa rồi trả lại kết quả
}
Sau đó, n u nh b n làm cho ph
ng th c ho t đ ng đ
c, s có cái hay! Đi u kì di u v s p x p tr n
ế
ư ạ
ươ
ứ
ạ ộ
ượ
ẽ
ề
ệ
ề ắ
ế
ộ
là nó có tính đ quy. lúc mà b n b t đ u s p x p các ph n bài, t i sao ph i kích ho t ph
ng
ệ
Ở
ạ
ắ ầ ắ
ế
ầ
ạ
ả
ạ
ươ
th c
ứ sort cũ và ch m ch p? Sao không kích ho t ph ng th c
ậ
ạ
ạ
ươ
ứ mergeSort m i toanh, đang đ c vi t?
ớ
ượ
ế
Đây không ch là m t ý t
ng t t, mà
ỉ
ộ
ưở
ố
c n thi t
ầ
ế ph i đ t đ c u th v hi u năng c a ch ng trình mà
ả ạ ượ ư
ế ề ệ
ủ
ươ
tôi đã h a. Nh ng đ ch
ng trình ho t đ ng, b n c n ph i có m t tr
ng h p c s . N u không, đ
ứ
ư
ể ươ
ạ ộ
ạ ầ
ả
ộ
ườ
ợ ơ ở ế
ệ
quy s mãi mãi. M t tr
ng h p c s đ n gi n là m t ph n bài v i 0 ho c 1 lá bài. N u
ẽ
ộ
ườ
ợ ơ ở ơ
ả
ộ
ầ
ớ
ặ
ế
nh
ư mergesort nh n đ c m t ph n bài nh nh v y, thì nó có th tr l i k t qu y nguyên, b i ph n
ậ
ượ
ộ
ầ
ỏ
ư ậ
ể ả ạ ế
ả
ở
ầ
bài nh này đã đ
c s p x p.
ỏ
ượ ắ
ế
Phiên b n đ quy c a
ả
ệ
ủ mergesort có th s trông nh sau:
ể ẽ
ư
public static
Deck mergeSort(Deck deck) {
// nếu cỗ bài chỉ gồm 0 hoặc 1 lá bài, thì trả lại nó
// tìm ra điểm giữa của cỗ bài
// chia cỗ bài thành hai phần bài
