Bagaimana untuk melakukan pengisihan dengan betul dalam Java

Dalam menganalisis kod sumber banyak projek Java sumber terbuka, saya mendapati kebanyakan pembangun melaksanakan pengisihan hanya dalam dua cara berbeza. Salah satunya adalah berdasarkan penggunaan kaedah sort()kelas Collectionsatau Arrays, dan satu lagi adalah berdasarkan penggunaan struktur data penyusunan sendiri seperti TreeMapdan TreeSet.

Menggunakan kaedah sort().

Jika anda perlu mengisih koleksi, kemudian gunakan 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());
	}
});

Jika anda perlu mengisih tatasusunan, gunakan 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());
	}
});

Kaedah ini sort()sangat mudah apabila koleksi atau tatasusunan sudah diisi dengan nilai.

Menggunakan struktur data pengisihan sendiri

Jika anda perlu mengisih senarai ( List) atau menetapkan ( Set), gunakan TreeSetstruktur pengisihan.

// 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);

Jika anda perlu mengisih kamus ( Map), gunakan TreeMapstruktur pengisihan. TreeMapdiisih mengikut kekunci ( 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);

Pendekatan di atas sangat berguna dalam kes di mana anda perlu melakukan sejumlah besar carian untuk elemen dalam koleksi. Struktur data pengisihan sendiri mempunyai kecekapan O(log(n))yang lebih baik daripada O(n). Ini bermakna apabila jumlah data dalam koleksi berganda, masa carian tidak berganda, tetapi meningkat dengan jumlah yang tetap .

Pendekatan yang buruk untuk menyusun masalah

Anda masih boleh mencari contoh di mana pengaturcara secara bebas menerangkan algoritma pengisihan. Pertimbangkan kod pengisihan yang dibentangkan di bawah (isih tatasusunan berganda dalam tertib menaik ). Kod ini bukan sahaja tidak cekap, tetapi juga tidak boleh dibaca. Dan terdapat banyak contoh sedemikian.

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