วิธีเรียงลำดับอย่างถูกต้องใน Java

จากการวิเคราะห์ซอร์สโค้ดของโปรเจ็กต์ OpenSource Java จำนวนมาก ฉันพบว่านักพัฒนาส่วนใหญ่ใช้การเรียงลำดับด้วยวิธีที่แตกต่างกันเพียงสองวิธีเท่านั้น หนึ่งในนั้นขึ้นอยู่กับการใช้เมธอดsort()คลาสCollectionsหรือ และ อีก Arraysอันขึ้นอยู่กับการใช้โครงสร้างข้อมูลที่เรียงลำดับตัวเอง เช่นTreeMapและTreeSet

โดยใช้วิธี sort()

หากคุณต้องการจัดเรียงคอลเลกชัน ให้ใช้นามสกุล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());
	}
});

หากคุณต้องการเรียงลำดับอาร์เรย์ ให้ใช้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());
	}
});

วิธีการนี้sort()จะสะดวกมากเมื่อคอลเลกชันหรืออาร์เรย์เต็มไปด้วยค่าแล้ว

การใช้โครงสร้างข้อมูลการเรียงลำดับตัวเอง

หากคุณต้องการเรียงลำดับรายการ ( List) หรือตั้งค่า ( Set) ให้ใช้TreeSetโครงสร้างการเรียงลำดับ

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

หากคุณต้องการเรียงลำดับพจนานุกรม ( Map) ให้ใช้TreeMapโครงสร้างการเรียงลำดับ TreeMapจัดเรียงตามปุ่ม ( 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);

วิธีการข้างต้นมีประโยชน์มากในกรณีที่คุณจำเป็นต้องทำการค้นหาองค์ประกอบในคอลเลกชันเป็นจำนวนมาก โครงสร้างข้อมูลที่เรียงลำดับตัวเองมีประสิทธิภาพO(log(n))ที่ดีกว่าO(n). ซึ่งหมายความว่า เมื่อปริมาณข้อมูลในคอลเลกชันเพิ่มขึ้นเป็นสองเท่า เวลาในการค้นหาจะไม่เป็นสองเท่า แต่จะเพิ่มขึ้นตามจำนวน คง ที่

วิธีการเรียงลำดับปัญหาที่ไม่ดี

คุณยังคงพบตัวอย่างที่โปรแกรมเมอร์อธิบายอัลกอริทึมการเรียงลำดับได้อย่างอิสระ พิจารณารหัสการเรียงลำดับที่แสดงด้านล่าง (การเรียงลำดับอาร์เรย์คู่จากน้อยไปมาก ) รหัสนี้ไม่เพียงแต่ไม่มีประสิทธิภาพเท่านั้น แต่ยังไม่สามารถอ่านได้อีกด้วย และมีตัวอย่างมากมาย

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