Cách sắp xếp chính xác trong Java

Khi phân tích mã nguồn của nhiều dự án Java mã nguồn mở, tôi thấy rằng hầu hết các nhà phát triển triển khai việc sắp xếp chỉ theo hai cách khác nhau. Một trong số chúng dựa trên việc sử dụng phương thức sort()lớp Collectionsor Arrays, và cái còn lại dựa trên việc sử dụng các cấu trúc dữ liệu tự sắp xếp như TreeMapvà TreeSet.

Sử dụng phương thức sắp xếp()

Nếu bạn cần sắp xếp một bộ sưu tập, hãy sử dụng phương thức Collections.sort().

// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

Nếu bạn cần sắp xếp một mảng, hãy sử dụng Arrays.sort().

// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

Phương pháp này sort()rất thuận tiện khi bộ sưu tập hoặc mảng đã chứa đầy các giá trị.

Sử dụng cấu trúc dữ liệu tự sắp xếp

Nếu bạn cần sắp xếp một danh sách ( List) hoặc tập hợp ( Set), hãy sử dụng TreeSetcấu trúc sắp xếp.

// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);

Nếu bạn cần sắp xếp một từ điển ( Map), hãy sử dụng TreeMapcấu trúc sắp xếp. TreeMapsắp xếp theo khóa ( key).

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);

Cách tiếp cận trên rất hữu ích trong trường hợp bạn cần thực hiện một số lượng lớn tìm kiếm các phần tử trong một bộ sưu tập. Cấu trúc dữ liệu tự sắp xếp có hiệu quả O(log(n))tốt hơn O(n). Điều này có nghĩa là khi lượng dữ liệu trong bộ sưu tập tăng gấp đôi, thời gian tìm kiếm không tăng gấp đôi mà tăng theo một lượng không đổi .

Cách tiếp cận tồi để sắp xếp vấn đề

Bạn vẫn có thể tìm thấy các ví dụ trong đó các lập trình viên mô tả các thuật toán sắp xếp một cách độc lập. Hãy xem xét mã sắp xếp được trình bày bên dưới (sắp xếp một mảng kép theo thứ tự tăng dần ). Mã này không chỉ không hiệu quả mà còn không thể đọc được. Và có rất nhiều ví dụ như vậy.

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}