Nếu bạn đã từng nghe nói về các phương pháp sắp xếp trong lập trình, rất có thể đó là thuật toán sắp xếp bong bóng. Nó là một trong những nổi tiếng. Mọi lập trình viên đều biết sắp xếp bong bóng [hoặc ít nhất là nghe nói về nó khi học] không phải vì nó là thuật toán sắp xếp tốt nhất trên thế giới, mà là thuật toán dễ nhất. Thuật toán này thường được sử dụng cho mục đích học tập hoặc bạn có thể lấy nó làm nhiệm vụ trong Cuộc phỏng vấn Java Junior của mình. Thuật toán sắp xếp bong bóng của Java rất dễ hiểu, tuy nhiên nó không phải là một thuật toán hiệu quả. Dù sao, chúng ta hãy tìm ra nó.
sắp xếp là gì
Trước hết, bạn cần hiểu sắp xếp nói chung là gì và chúng ta có thể sắp xếp những gì trong chương trình Java. Nếu chúng ta có thể so sánh hai hoặc nhiều phần tử hoặc đối tượng theo bất kỳ thuộc tính nào của chúng, điều đó có nghĩa là chúng có thể được sắp xếp theo thuộc tính này. Ví dụ: các số theo thứ tự tăng dần hoặc giảm dần hoặc các từ theo bảng chữ cái. Do đó, các yếu tố phải được so sánh với nhau. Nhân tiện, các yếu tố của cái gì? Trong Java, chúng ta có thể so sánh các phần tử của Collections. Ví dụ: chúng ta có thể sắp xếp Array hoặc ArrayList của số nguyên, Chuỗi, v.v.
Sắp xếp bong bóng hoạt động như thế nào
Giả sử, chúng ta cần sắp xếp một mảng các số nguyên theo thứ tự tăng dần, tức là từ số nhỏ nhất đến số lớn nhất. Đầu tiên, chúng ta sẽ đi dọc theo toàn bộ mảng và so sánh từng 2 phần tử lân cận. Nếu chúng sai thứ tự [hàng xóm bên trái lớn hơn hàng xóm bên phải], chúng tôi đổi chỗ cho chúng. Ở lần vượt qua đầu tiên ở cuối sẽ xuất hiện phần tử lớn nhất [nếu ta sắp xếp theo thứ tự tăng dần]. Bạn có thể nói, yếu tố lớn nhất “bật lên”. Đó là lý do của tên thuật toán sắp xếp bong bóng. Chúng tôi lặp lại bước đầu tiên từ phần tử đầu tiên đến phần tử tiếp theo. Chúng tôi đã có yếu tố lớn thứ hai ở vị trí tiếp theo đến cuối cùng. Và như thế. Chúng ta có thể cải thiện thuật toán một chút bằng cách kiểm tra xem có ít nhất một trao đổi ở bước trước được thực hiện hay không. Nếu không, chúng tôi dừng chạy dọc theo mảng.
Trước hết chúng ta cần phân biệt kiểu nguyên thủy [Primitive type] và kiểu tham chiếu [reference type] trong java.
Trong Java chúng ta có 8 kiểu nguyên thủy.
- Kiểu nguyên thủy [Primitive type]
Type
Bit/Bytes
Range
boolean
1 bit
True or False
char
16 bit/ 2 bytes
0 to 65535
byte
8 bit/ 1 byte
-128 to 127
short
16 bit/ 2 bytes
-32768 to 32767
int
32 bits/ 4 bytes
-2147483648 to 2147483647
long
64 bits/ 8 bytes
-9,223,372,036,854,775,808 to -9,223,372,036,854,775,808 [-2^63 to -2^63]
float
32 bits/ 4 bytes
-3.4028235 x 10^38 to 3.4028235 x 10^38
double
64 bits/ 8 bytes
-1.7976931348623157 x 10^308 to 1.7976931348623157 x 10^308
Tất cả các kiểu khác đều mở rộng từ Object, chúng là các kiểu tham chiếu.
2. Kiểu nguyên thủy lưu trữ thế nào trên bộ nhớ
Trước hết bạn phải hiểu rằng, Java không đảm bảo rằng mỗi biến sẽ tương ứng với một vị trí trên bộ nhớ. chẳng hạn Java sẽ tối ưu theo cách biến 'i' sẽ được lưu trữ trên bộ đăng ký [register], hoặc thậm trí không được lưu trữ ở đâu cả, nếu trình biên dịch nhận thấy rằng bạn không bao giờ sử dụng giá trị của nó, hoặc nó có thể được dõi theo thông qua code và sử dụng các giá trị phù hợp một cách trực tiếp.
Xem một đoạn code:
// Tạo biến 'a', và gán giá trị 100.
int a = 100;
// Gán giá trị mới cho 'a'
a = 200;
// Tạo biến 'b', gán b = a.
int b = a;Khi đó Java thực hiện các thao tác sau:
- TODO
3. Kiểu tham chiếu lưu trữ thế nào trên bộ nhớ
Khi bạn sử dụng toán tử new [Ví dụ new Object[]], Java sẽ tạo ra một thực thể mới trên bộ nhớ. Bạn khai báo một biến và khởi tạo giá trị của nó thông qua toán tử new, chẳng hạn Object a = new Object[]; Java sẽ tạo ra một thực thể mới trong bộ nhớ, và một tham chiếu 'a' trỏ tới vị trí bộ nhớ của thực thể vừa được tạo ra.
Khi bạn khai báo một biến b Object b = a; không có thực thể nào được tạo ra trong bộ nhớ, Java chỉ tạo ra một tham chiếu 'b', trỏ tới vị cùng vị trí mà 'a' đang trỏ tới.
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;- TODO
4. Các cách so sánh trong Java
Trong Java có 2 kiểu so sánh:
- Sử dụng toán tử ==
- Sử dụng phương thức [method] equals[..]
Toán tử == dùng so sánh các kiểu nguyên thủy và các kiểu tham chiếu. Toán tử equals[..] là một phương thức chỉ dùng cho các kiểu tham chiếu.
5. So sánh các kiểu nguyên thủy
Với kiểu nguyên thủy chúng ta chỉ có duy nhất một cách so sánh bằng toán tử ==, các kiểu nguyên thủy so sánh với nhau thông qua giá trị của chúng.
// Tạo ra một biến 'a', gán bởi giá trị 200 cho nó.
// Một vùng bộ nhớ [1] được tạo ra chứa giá trị 200.
int a = 200;
// Tạo ra một biến 'b', gán giá trị 200 cho nó.
// Một vùng bộ nhớ [2] được tạo ra chứa giá trị 200.
int b = 200;
// Mặc dù 'a' và 'b' trỏ tới 2 vùng bộ nhớ khác nhau.
// So sánh a == b sẽ cho kết quả true.
// Vì kiểu nguyên thủy so sánh với nhau dựa trên giá trị.
boolean c = [a == b];6. So sánh các kiểu tham chiếu
Sử dụng toán tử == so sánh các kiểu tham chiếu
Khi bạn so sánh 2 đối tượng tham chiếu theo toán tử ==, có nghĩa là so sánh vị trí mà 2 đối tượng tham chiếu này trỏ tới. Về bản chất là kiểm tra xem 2 tham chiếu đó có cùng trỏ tới một thực thể trên bộ nhớ hay không.
Hãy xem ví dụ:
ReferenceEeDemo.java
package org.o7planning.tutorial.comparation;
public class ReferenceEeDemo {
public static void main[String[] args] {
// Chú ý: Với String 2 cách khởi tạo đối tượng dưới đây là không giống nhau:
String str1 = "String 1";
String str2 = new String["String 1"];
// Toán tử 'new' tạo ra vùng bộ nhớ [1]
// chứa String "This is text"
// Và 's1' là một tham chiếu trỏ đến vùng [1].
String s1 = new String["This is text"];
// Toán tử 'new' tạo ra vùng bộ nhớ [2]
// Chứa String "This is text"
// Và 's2' là một tham chiếu trỏ đến [2]
String s2 = new String["This is text"];
// Sử dụng toán tử == so sánh 's1' và 's2'.
// Kết quả ra false.
// Nó rõ ràng khác với suy nghĩ của bạn.
// Lý do là với kiểu tham chiếu
// toán tử == so sánh vị trí trên bộ nhớ mà chúng trỏ tới.
boolean e1 = [s1 == s2]; // false
System.out.println["s1 == s2 ? " + e1];
// Không có toán tử 'new' nào.
// Java tạo ra một tham chiếu có tên 'obj'
// Và trỏ tới vùng bộ nhớ mà 's1' đang trỏ tới.
Object obj = s1;
// 2 tham chiếu 'obj' và 's1' đang cùng trỏ tới 1 vùng bộ nhớ.
// Kết quả trả về là true.
boolean e2 = [obj == s1]; // true
System.out.println["obj == s1 ? " + e2];
}
}Kết quả chạy chương trình
s1 == s2 ? false
obj == s1 ? trueSử dụng equals[..] so sánh các kiểu tham chiếu
StringComparationDemo.java
package org.o7planning.tutorial.comparation;
public class StringComparationDemo {
public static void main[String[] args] {
String s1 = new String["This is text"];
String s2 = new String["This is text"];
// So sánh s1 và s2 thông qua phương thức equals[..]
boolean e1 = s1.equals[s2];
// Kết quả sẽ là true
System.out.println["first comparation: s1 equals s2 ? " + e1];
s2 = new String["New s2 text"];
boolean e2 = s1.equals[s2];
// Kết quả sẽ là false
System.out.println["second comparation: s1 equals s2 ? " + e2];
}
}Kết quả chạy chương trình:
first comparation: s1 equals s2 ? true
second comparation: s1 equals s2 ? falseGhi đè phương thức equals[Object]
Phương thức equals[Object] là phương thức có sẵn của class Object, mọi class con đều được thừa kế method này. Trong một số tình huống bạn có thể ghi đè method này tại class con.
NumberOfMedals.java
package org.o7planning.tutorial.comparation.equals;
// Số lượng Huy chương
public class NumberOfMedals {
// Số huy chương vàng
private int goldCount;
// Số huy chương bạc.
private int silverCount;
// Số huy chương đồng
private int bronzeCount;
public NumberOfMedals[int goldCount, int silverCount, int bronzeCount] {
this.goldCount = goldCount;
this.silverCount = silverCount;
this.bronzeCount = bronzeCount;
}
public int getGoldCount[] {
return goldCount;
}
public int getSilverCount[] {
return silverCount;
}
public int getBronzeCount[] {
return bronzeCount;
}
// Ghi đè phương thức equals[Object] của lớp Object.
@Override
public boolean equals[Object other] {
// Nếu other = null thì trả về false.
if [other == null] {
return false;
}
// Nếu 'other' không phải là kiểu NumberOfMedals
// thì trả về false.
if [![other instanceof NumberOfMedals]] {
return false;
}
NumberOfMedals otherNoM = [NumberOfMedals] other;
if [this.goldCount == otherNoM.goldCount && this.silverCount == otherNoM.silverCount
&& this.bronzeCount == otherNoM.bronzeCount] {
return true;
}
return false;
}
}NumberOfMedalsComparationDemo.java
package org.o7planning.tutorial.comparation.equals;
public class NumberOfMedalsComparationDemo {
public static void main[String[] args] {
// Thành tích của đội Mỹ.
NumberOfMedals american = new NumberOfMedals[40, 15, 15];
// Thành tích của đội Nhật.
NumberOfMedals japan = new NumberOfMedals[10, 5, 20];
// Thành tích của đội Hàn Quốc
NumberOfMedals korea = new NumberOfMedals[10, 5, 20];
System.out.println["Medals of American equals Japan ? " + american.equals[japan]];
System.out.println["Medals of Korea equals Japan ? " + korea.equals[japan]];
}
}Kết quả chạy ví dụ
Medals of American equals Japan ? false
Medals of Korea equals Japan ? true7. Ví dụ sắp xếp một mảng String
String vốn là một class mà các đối tượng của nó có thể so sánh với nhau, theo quy tắc chữ cái. Ví dụ sau đây minh họa cách sắp xếp một mảng String sử dụng các phương thức tiện ích có sẵn trong Java.
StringArraySortingDemo.java
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;0
Kết quả chạy ví dụ
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;1
8. Các đối tượng có thể so sánh với nhau [Comparable]
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;2
Actor.java
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;3
ActorSortingDemo.java
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;4
Kết quả chạy ví dụ
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;5
Sử dụng Arrays.sort[Object[]] để sắp xếp ví dụ trên:
ActorSortingDemo2.java
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;6
9. Sắp xếp một danh sách [List]
Bạn có thể tham khảo thêm tài liệu Java Collection Framework tại:
Ví dụ:
ListSortingDemo.java
// Khai báo và khởi tạo đối tượng.
Object a = new Object[];
// Gán giá trị mới cho đối tượng 'a'.
a = new String["Text"];
// Khai báo đối tượng 'b', và gán 'a' cho nó.
Object b = a;7
10. Sắp xếp sử dụng bộ so sánh [Comparator]
Các ví dụ trên chúng ta sắp xếp một mảng hoặc một danh sách. Bản thân các phần tử của nó có khả năng so sánh với nhau [Do thi hành interface Comparable]. Câu hỏi đặt ra với các đối tượng mà class của nó không thi hành interface Comparable, thì có thể sắp xếp được không. Trong trường hợp này bạn cần cung cấp 1 bộ so sánh [Comparator] nó là quy tắc để sắp xếp các đối tượng kia.