So sánh và sắp xếp trong Java
Công ty Vĩnh Cửu tuyển dụng lập trình viên Java

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- Stack và Heap là gì?

Biến của bạn được lưu trữ trên Stack (Ngăn xếp) hoặc Heap, vậy Stack và Heap là gì?
  • TODO

3- 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:
// Create a variable 'a', and assin valud to it.
int a = 100;

// Assign new value
a = 200;

// Create variable b, assign value a
int b = a;
 
Khi đó Java thực hiện các thao tác sau:
  • TODO

4- 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();

// Khởi tạo lại đối tượng
a = new String("Text");

// Khai báo đối tượng 'b' và gán nó bằng đối tượng 'a'.
Object b =  a;
  • TODO

5- Các kiểu so sánh trong Java

Trong Java có 2 kiểu so sánh:
  • Sử dụng toán tử ==
  • Sử dụng 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à method chỉ dùng cho các kiểu tham chiếu.

6- 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
// 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.
// 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 là giá trị.
boolean c = (a == b);

7- So sánh các kiểu tham chiếu

7.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 sau là không giống nhau:
     // Bạn có thể xem trong tài liệu nói về String.
     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 (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í 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 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ề true
     boolean e2 = (obj == s1); // true

     System.out.println("obj == s1 ? " + e2);
 }
}
Kết quả chạy chương trình

7.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 method 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:

7.3- Ghi đè method 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 đè method equals(Object) của class Object.
   @Override
   public boolean equals(Object other) {
       // Nếu đối tượng so sánh null trả về false.
       if (other == null) {
           return false;
       }
       // Nếu đối tượng cần so sánh không phải kiểu NumberOfMedals
       // thì trả về false.
       if (!(other instanceof NumberOfMedals)) {
           return false;
       }
       // Ép kiểu
       NumberOfMedals otherNoM = (NumberOfMedals) other;
       // Nếu số lượng huy chương vàng, bạc, đồng bằng nhau
       // trả về true.
       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ụ

8- 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 method tĩnh của class 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ụ

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

// Bạn viết một class 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 sắp xếp theo họ trước rồi mới tới tên.
// Lúc này nẩy sinh ra tình huống cần phải so sánh các đối tượng Actor.

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 class 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 lastName trước, firstName sau.
  @Override
  public int compareTo(Actor other) {
      // String có thể so sánh được với nhau
      // Vì String thi hành interface Comparable<String>
      // So sánh lastName giữa 2 đối tượng.
      int value = this.lastName.compareTo(other.lastName);

      // Nếu lastName của 2 đối tượng không bằng nhau.
      if (value != 0) {
          return value;
      }
      // Trường hợp lastName của 2 đối tượng giống nhau.
      // So sánh tiếp 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 };

      // Chúng ta 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 Actor.
      // Duyệt trên các phần tử của mảng.
      for (int i = 0; i < actors.length; i++) {

          for (int j = i + 1; j < actors.length; j++) {
              // Nếu Actor sau nhỏ hơn Actor trước
              // 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;
              }
          }
      }
      // Bây giờ thì 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());
      }

  }
}
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);
       
       
       // Bây giờ thì 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());
       }

   }
}

10- 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ó thể so sánh với nhau.
       List<Actor> actors = new ArrayList<Actor>();

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

       // Sử dụng 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());
       }

   }
}

11- 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;

// Bộ so sánh này thi hành interface Comparator<Person>
// Chuyên so sánh các đối tượng Person.
public class PersonComparator implements Comparator<Person> {

  // Ghi đè method compare.
  // Nêu rõ quy tắc so sánh giữa 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 null, coi như o2 lớn hơn
      if (o1 == null) {
          return -1;
      }
      // Nếu o2 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;
      }
      // Trường hợp bằng tuổi, so sánh tiếp fullName
      // So sánh theo Alphabet.
      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 cần 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>)
       // Cung cấp rõ một bộ so sánh.
       Arrays.sort(array, new PersonComparator());

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

       // Trường hợp 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>)
       // Cung cấp rõ một 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ụ: