Java: Sắp xếp trong collection
Giải phóng thời gian, khai phóng năng lực
Thực ra việc sắp xếp trong collection của java là một vấn đề rất cũ, nhưng thường trong các câu hỏi phỏng vấn về java ứng viên rất hay bị hỏi về vấn đề này. Vì vậy mình mong post này sẽ giúp được một số ứng viên chẳng may bị hỏi đến lúc phỏng vấn. Lớp Collections cung cấp các phương thức tĩnh (static) cho việc sắp xếp các phần tử của collection. Chúng ta có thể sắp xếp các phần tử là:
- Các đối tượng kiểu String
- Các đối tượng Wrapper
- Các đối tượng do người dùng tự định nghĩa(User-defined)
Phương thức của Collections class dùng cho việc sắp xếp các phần tử của List:
public void sort(List list): được sử dụng để sắp xếp các phần tử của List. Các phần tử của List phải là kiểu Comparable.
Lưu ý: lớp String và các lớp Wrapper thực thi interface Comparable vì vậy nên mặc định là nó có thể sắp xếp được.
Ví dụ sắp xếp List chứa các đối tượng String
import java.util.*; class TestSortString { public static void main(String args[]) { ArrayList<String> al = new ArrayList<String>(); al.add("PHP"); al.add("Java"); al.add("Laravel"); al.add("Android"); Collections.sort(al); Iterator itr = al.iterator(); while (itr.hasNext()) { System.out.println(itr.next()); } } }
Kết quả:
Android Java Laravel PHP
Ví dụ về sắp xếp List chứa các đối tượng Wrapper
import java.util.*; class TestSortWrapper { public static void main(String args[]) { ArrayList al = new ArrayList(); al.add(Integer.valueOf(456)); al.add(Integer.valueOf(123)); al.add(789); // sẽ được convert thành Integer.valueOf(789) Collections.sort(al); Iterator itr = al.iterator(); while (itr.hasNext()) { System.out.println(itr.next()); } } }
Kết quả:
101 201 230
interface Comparable
interface Comparable được sử dụng để chỉ ra thứ tự của các đối tượng do người dùng tự định nghĩa (User-defined). Comparable chỉ chứa duy nhất một phương thức tên là compareTo(Object). Nó cung cấp duy nhất một trình tự sắp xếp ví dụ như bạn chỉ có thể sắp các phần tử của đối tượng Student theo id hoặc name hoặc age, ...
Ví dụ:
import java.util.ArrayList; import java.util.Collections; class Student implements Comparable<Student> { int id; String name; int age; Student(int id, String name, int age) { this.id = id; this.name = name; this.age = age; } //sắp xếp tăng dần theo thuộc tính age public int compareTo(Student Student) { if (age == Student.age) return 0; else if (age > Student.age) return 1; else return -1; } } class TestSortComparable { public static void main(String args[]) { ArrayList<Student> al = new ArrayList<Student>(); al.add(new Student(103, "Phong", 18)); al.add(new Student(102, "Minh", 20)); al.add(new Student(101, "Ninh", 19)); //Sắp xếp list sinh viên Collections.sort(al); for (Student stu : al) { System.out.println(stu.id + " " + stu.name + " " + stu.age); } } }
Kết quả:
103 Phong 18 101 Ninh 19 102 Minh 20
interface Comparator
interface Comparator được sử dụng để chỉ ra thứ tự của các đối tượng do người dùng tự định nghĩa (User-defined). Comparator định nghĩa hai phương thức là compare(Object obj1, Object obj2) và equals(Object element). Nó cung cấp nhiều trình tự sắp xếp ví dụ như bạn có thể sắp xếp các phần tử của đối tượng Employee theo id, name, age, ...
public int compare(Object obj1, Object obj2): so sánh hai đối tượng với nhau.
public void sort(List list, Comparator c): phương thức của Collections được sử dụng để sắp xếp các phần tử của list dựa trên Comparator.
Ví dụ:
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; class Employee { int id; String name; short age; Employee(int id, String name, short age) { this.id = id; this.name = name; this.age = age; } } class AgeComparator implements Comparator<Employee> { public int compare(Employee emp1, Employee emp2) { if (emp1.age == emp2.age) return 0; else if (emp1.age > emp2.age) return 1; else return -1; } } class NameComparator implements Comparator<Employee> { public int compare(Employee emp1, Employee emp2) { return emp1.name.compareTo(emp2.name); } } class IdComparator implements Comparator<Employee> { public int compare(Employee emp1, Employee emp2) { if (emp1.id == emp2.id) return 0; else if (emp1.id > emp2.id) return 1; else return -1; } } class TestSortComparator { public static void main(String args[]) { ArrayList<Employee> al = new ArrayList<Employee>(); al.add(new Employee(103, "Phong", (short) 18)); al.add(new Employee(102, "Minh", (short) 20)); al.add(new Employee(101, "Ninh", (short) 19)); System.out.println("Sắp xếp theo thuộc tính name:"); Collections.sort(al, new NameComparator()); for (Employee st : al) { System.out.println(st.id + " " + st.name + " " + st.age); } System.out.println("Sắp xếp theo thuộc tính age:"); Collections.sort(al, new AgeComparator()); for (Employee st : al) { System.out.println(st.id + " " + st.name + " " + st.age); } System.out.println("Sắp xếp theo thuộc tính id:"); Collections.sort(al, new IdComparator()); for (Employee st : al) { System.out.println(st.id + " " + st.name + " " + st.age); } } }
Kết quả:
Sắp xếp theo thuộc tính name: 102 Minh 20 101 Ninh 19 103 Phong 18 Sắp xếp theo thuộc tính age: 103 Phong 18 101 Ninh 19 102 Minh 20 Sắp xếp theo thuộc tính id: 101 Ninh 19 102 Minh 20 103 Phong 18
So sánh Comparable và Comparator
Comparable và Comparator đều là những interface được sử dụng để sắp xếp các phần tử trong collection. Nhưng chúng có vài đặc điểm khác nhau như sau:
Comparable | Comparator |
---|---|
Cung cấp duy nhất một trình tự sắp xếp | Cung cấp nhiều trình tự sắp xếp |
Ảnh hưởng đến class gốc (phải thực thi Comparable) | Không ảnh hưởng đến class gốc |
Cung cấp phương thức compareTo() | Cung cấp phương thức compare() |
Nằm trong java.lang (không cần phải import) | Nằm trong java.util (phải import) |
Sắp xếp sử dụng Collections.sort(List) | Sắp xếp sử dụng Collections.sort(List, Comparator) |
Giải phóng thời gian, khai phóng năng lực