So sánh và sắp xếp trong Java

Xem thêm các chuyên mục:

1- Kiểu nguyên thủy và kiểu tham chiếu trong Java.

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

6.1- 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

6.2- Sử 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:

6.3- Ghi đè 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ụ

7- 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
package org.o7planning.tutorial.sorting;

import java.util.Arrays;

public class StringArraySortingDemo {

	public static void main(String[] args) {
		String[] fruits = new String[] { "Pineapple", "Apple", "Orange", "Banana" };

		// Sử dụng phương thức tĩnh của lớp Arrays để sắp xếp.
		// Arrays.sort(Object[])
		Arrays.sort(fruits);

		for (int i = 0; i < fruits.length; i++) {
			System.out.println("fruits " + i + " : " + fruits[i]);
		}
	}

}
Kết quả chạy ví dụ

8- Các đối tượng có thể so sánh với nhau (Comparable)

// Bạn viết một lớp mô phỏng một diễn viên (Actor).
// Bạn muốn sắp xếp thứ tự các diễn viên theo nguyên tắc:
// So sánh họ (lastName) trước, rồi so sánh theo tên (firstName). 
public class Actor {

	// Tên
	private String firstName;
	// Họ
	private String lastName;

}
Actor.java
package org.o7planning.tutorial.sorting;

// Để so sánh được với nhau, lớp Actor cần thi hành interface Comparable.
public class Actor implements Comparable<Actor> {

	private String firstName;
	private String lastName;

	public Actor(String firstName, String lastName) {
		this.firstName = firstName;
		this.lastName = lastName;
	}

	public String getFirstName() {
		return firstName;
	}

	public String getLastName() {
		return lastName;
	}

	// So sánh với một đối tượng Actor khác
	// Theo nguyên tắc so sánh lastName trước,
	// sau đó so sánh firstName.
	@Override
	public int compareTo(Actor other) {

		// So sánh 2 String.
		int value = this.lastName.compareTo(other.lastName);

		// Nếu lastName của 2 đối tượng là không bằng nhau.
		if (value != 0) {
			return value;
		}
		// Nếu lastName của 2 đối tượng là giống nhau.
		// Thì so sánh fistName.
		value = this.firstName.compareTo(other.firstName);
		return value;
	}

}
ActorSortingDemo.java
package org.o7planning.tutorial.sorting;

public class ActorSortingDemo {

	public static void main(String[] args) {

		Actor actor1 = new Actor("Mischa", "Barton");
		Actor actor2 = new Actor("Christian", "Bale");
		Actor actor3 = new Actor("Joan", "Collins");
		Actor actor4 = new Actor("Gemma", "Arterton");
		Actor actor5 = new Actor("Daniel", "Craig");

		Actor[] actors = new Actor[] { actor1, actor2, actor3, actor4, actor5 };

		// Sử dụng một thuật toán để sắp xếp lại mảng trên.
		// Sắp xếp tăng dần các đối tượng Actor.
		for (int i = 0; i < actors.length; i++) {

			for (int j = i + 1; j < actors.length; j++) {
				// Nếu actors[j] < actors[i]
				// Thì thực hiện việc tráo đổi vị trí với nhau.
				if (actors[j].compareTo(actors[i]) < 0) {
					// Sử dụng một biến tạm thời.
					Actor temp = actors[j];
					actors[j] = actors[i];
					actors[i] = temp;
				}
			}
		}
		// On ra các phần tử mảng.
		for (int i = 0; i < actors.length; i++) {
			System.out.println(actors[i].getFirstName() + "  " + actors[i].getLastName());
		}

	}

}
Kết quả chạy ví dụ
Sử dụng Arrays.sort(Object[]) để sắp xếp ví dụ trên:
ActorSortingDemo2.java
package org.o7planning.tutorial.sorting;

import java.util.Arrays;

public class ActorSortingDemo2 {

	public static void main(String[] args) {

		Actor actor1 = new Actor("Mischa", "Barton");
		Actor actor2 = new Actor("Christian", "Bale");
		Actor actor3 = new Actor("Joan", "Collins");
		Actor actor4 = new Actor("Gemma", "Arterton");
		Actor actor5 = new Actor("Daniel", "Craig");

		Actor[] actors = new Actor[] { actor1, actor2, actor3, actor4, actor5 };

		// Sử dụng Arrays.sort(Object[]) để sắp xếp.
		Arrays.sort(actors);

		// In ra các phần tử mảng.
		for (int i = 0; i < actors.length; i++) {
			System.out.println(actors[i].getFirstName() + "  " + actors[i].getLastName());
		}

	}
}

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
package org.o7planning.tutorial.sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ListSortingDemo {

	public static void main(String[] args) {

		Actor actor1 = new Actor("Mischa", "Barton");
		Actor actor2 = new Actor("Christian", "Bale");
		Actor actor3 = new Actor("Joan", "Collins");
		Actor actor4 = new Actor("Gemma", "Arterton");
		Actor actor5 = new Actor("Daniel", "Craig");

		// Một danh sách chứa các phần tử có khả năng so sánh với nhau.
		// (Comparable)
		List<Actor> actors = new ArrayList<Actor>();

		actors.add(actor1);
		actors.add(actor2);
		actors.add(actor3);
		actors.add(actor4);
		actors.add(actor5);

		// Sử dụng phương thức Collections.sort(List)
		// để sắp xếp một danh sách (List)
		Collections.sort(actors);

		for (Actor actor : actors) {
			System.out.println(actor.getFirstName() + "  " + actor.getLastName());
		}

	}

}

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.
Person.java
package org.o7planning.tutorial.comparator;

public class Person {

  private int age;
  private String fullName;

  public Person(String fullName, int age) {
      this.fullName = fullName;
      this.age = age;
  }

  public int getAge() {
      return age;
  }

  public String getFullName() {
      return fullName;
  }
}
PersonComparator.java
package org.o7planning.tutorial.comparator;

import java.util.Comparator;

// Lớp này thực hiện interface Comparator<Person>.
// Nó là một quy tắc để so sánh các đối tượng Person.
public class PersonComparator implements Comparator<Person> {

	// Ghi đè (override) phương thức compare.
	// Nêu rõ quy tắc so sánh 2 đối tượng Person.
	@Override
	public int compare(Person o1, Person o2) {
		// Hai đối tượng null coi như bằng nhau.
		if (o1 == null && o2 == null) {
			return 0;
		}
		// Nếu o1 là null, coi như o2 lớn hơn
		if (o1 == null) {
			return -1;
		}
		// Nếu o2 là null, coi như o1 lớn hơn.
		if (o2 == null) {
			return 1;
		}
		// Nguyên tắc:
		// Sắp xếp tăng dần theo tuổi.
		int value = o1.getAge() - o2.getAge();
		if (value != 0) {
			return value;
		}
		// Nếu tuổi giống nhau, thì so sánh fullName.
		// So sánh theo Alphabet (chữ cái).
		value = o1.getFullName().compareTo(o2.getFullName());
		return value;
	}

}
ComparatorSortingDemo.java
package org.o7planning.tutorial.comparator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ComparatorSortingDemo {

	public static void main(String[] args) {
		Person person1 = new Person("Marry", 20);
		Person person2 = new Person("Tom", 21);
		Person person3 = new Person("Daniel", 21);
		Person person4 = new Person("Mischa", 18);
		Person person5 = new Person("Christian", 20);

		// Một mảng chưa được sắp xếp.
		Person[] array = new Person[] { person1, person2, person3, person4, person5 };

		// Sắp xếp mảng, sử dụng: <T> Arrays.sort(T[],Comparator<? supers T>).
		// Và cung cấp một Comparator (Bộ so sánh).
		Arrays.sort(array, new PersonComparator());

		for (Person person : array) {
			System.out.println("Person: " + person.getAge() + " / " + person.getFullName());
		}

		System.out.println("------------------------");

		// Đối với một danh sách:
		List<Person> list = new ArrayList<Person>();
		list.add(person1);
		list.add(person2);
		list.add(person3);
		list.add(person4);
		list.add(person5);

		// Sắp xếp danh sách sử dụng:
		// <T> Collections.sort(List<T>, Comparator<? supers T>).
		// Và cung cấp một Comparator (Bộ so sánh).
		Collections.sort(list, new PersonComparator());

		for (Person person : list) {
			System.out.println("Person: " + person.getAge() + " / " + person.getFullName());
		}
	}

}
Kết quả chạy ví dụ:

Xem thêm các chuyên mục: