แนวคิดอัลกอริทึมการเรียงลำดับอย่างรวดเร็ว
การเรียงลำดับอย่างรวดเร็วนั้นขึ้นอยู่กับการใช้งานแบบเรียกซ้ำ แนวคิดมีดังนี้:
1. เลือกค่าที่เหมาะสม (ค่าอุดมคติดีที่สุด แต่ค่าแรกในอาร์เรย์มักใช้ในการใช้งาน) ซึ่งเรียกว่า "เดือย"
2. ขึ้นอยู่กับค่านี้แบ่งอาร์เรย์ออกเป็นสองส่วนส่วนเล็ก ๆ ทางด้านซ้ายและส่วนใหญ่ทางด้านขวา
3. แน่นอนว่าหลังจากรอบดังกล่าวตำแหน่งของเดือยนี้จะต้องอยู่ในตำแหน่งสุดท้าย
4. ทำซ้ำกระบวนการข้างต้นสำหรับสอง subarrays จนกว่าจะมีเพียงหนึ่งองค์ประกอบต่ออาร์เรย์
5. การเรียงลำดับเสร็จสมบูรณ์
วิธีการใช้งานพื้นฐาน:
โมฆะสาธารณะคงที่ public Quicksort (int [] arr) {qsort (arr, 0, arr.length-1);} void qsort แบบคงที่ส่วนตัว (int [] arr, int ต่ำ, int สูง) {ถ้า (ต่ำ <สูง) {int pivot = พาร์ติชัน (arr, ต่ำ, สูง, สูง); // แบ่งอาร์เรย์ออกเป็นสองส่วน QSort (arr, ต่ำ, pivot-1); // เรียงลำดับ subarray qsort ด้านซ้าย (arr, pivot+1, สูง); // เรียงลำดับ subarray ที่ถูกต้องซ้ำ}} พาร์ติชัน int คงที่ส่วนตัว (int [] arr, int ต่ำ, int สูง) {int pivot = arr [ต่ำ]; // pivot Record ในขณะที่ (ต่ำ <สูง) {ในขณะที่ (ต่ำ <high && arr [สูง]> = pivot) -สูง; arr [ต่ำ] = arr [สูง]; // swap บันทึกเล็กกว่าเดือยไปทางซ้ายในขณะที่ (ต่ำ <high && arr [ต่ำ] <= pivot) ++ ต่ำ; arr [สูง] = arr [ต่ำ]; // swap บันทึกที่เล็กกว่าเดือยไปทางด้านขวา} // สแกนเสร็จสมบูรณ์และเดือยอยู่ในสถานที่ arr [ต่ำ] = pivot; // ส่งคืนตำแหน่งของเดือยให้กลับต่ำ;}ใช้ยาสามัญเพื่อใช้อัลกอริทึมการสั่งซื้ออย่างรวดเร็ว
ด้านล่างนี้เป็นคลาส Quicksort ซึ่งมีฟังก์ชันคงที่ () ซึ่งสามารถเรียงลำดับอาร์เรย์ทุกประเภท หากเป็นอาร์เรย์ของประเภทวัตถุประเภทวัตถุจะต้องใช้อินเทอร์เฟซที่เปรียบเทียบได้เพื่อให้สามารถใช้ฟังก์ชันการเปรียบเทียบเพื่อเปรียบเทียบ
ใช้อัลกอริทึมการเรียงลำดับแถวที่รวดเร็วที่สุดและไม่มีการประมวลผลการเพิ่มประสิทธิภาพ
ซอร์สโค้ดมีดังนี้:
นำเข้า java.util.linkedList; นำเข้า java.util.list; นำเข้า java.util.listiterator; นำเข้า java.util.random; Public Class Quicksort {@suppresswarnings ("ไม่ถูกตรวจสอบ") // แก้ไขต้นแบบฟังก์ชันด่วนแถวข้างบนเพื่อให้สามารถเรียงลำดับอาร์เรย์ของวัตถุประเภทใดก็ได้ ฟังก์ชั่นนี้ใช้ภายในและอินเทอร์เฟซฟังก์ชั่นการเรียงลำดับภายนอกคือการเรียงลำดับ () ฟังก์ชั่นการเรียงลำดับต้องการให้วัตถุต้องใช้อินเทอร์เฟซที่เปรียบเทียบได้ซึ่งสามารถให้การตรวจจับประเภทเวลารวบรวมดูบทความต่อไปนี้ Void Quicksort ส่วนตัว (วัตถุ [] in, int เริ่มต้น, int end) {ถ้า (เริ่มต้น == end || เริ่มต้น == (end-1)) กลับ; วัตถุ p = ใน [เริ่มต้น]; int a = เริ่ม +1; int b = a; สำหรับ (; b <end; b ++) {// อาร์เรย์ประเภทวัตถุนี้จะต้องใช้อินเตอร์เฟสที่เปรียบเทียบได้เพื่อให้คุณสามารถใช้ฟังก์ชันเปรียบเทียบสำหรับการเปรียบเทียบถ้า (((เปรียบเทียบ <jobch>) ใน [b]). compareto (p) <0) {if (a == b) {a ++; ดำเนินการต่อ;} วัตถุอุณหภูมิ = ใน [a]; ใน [a] = ใน [b]; ใน [b] = อุณหภูมิ; A ++; }} ใน [เริ่มต้น] = ใน [A-1]; ใน [A-1] = P; ถ้า (A-1> เริ่มต้น) {QuickSort (ใน, เริ่มต้น, a); } if (end-1> a) {Quicksort (in, a, end); } กลับ; } // ใช้ยาชื่อสามัญเพื่อเรียงลำดับอาร์เรย์วัตถุใด ๆ อาร์เรย์ประเภทวัตถุจะต้องใช้อินเตอร์เฟสที่เทียบเท่ากับสแตติกสาธารณะ <t ขยายเทียบเท่า <? super t >> void sort (t [] อินพุต) {quicksort (อินพุต, 0, input.length); } // เพิ่มฟังก์ชั่นของวัตถุรายการเรียงลำดับอ้างอิงถึงฟังก์ชั่นการเรียงลำดับ () ของคลาส java.util.collections ใน Java สาธารณะคงที่ <t ขยายเปรียบเทียบได้ <? Super t >> Void Sort (รายการ <t> รายการ) {Object [] t = list.toarray (); // แปลงรายการเป็นอาร์เรย์ Quicksort (t, 0, t.length); // เรียงลำดับอาร์เรย์ // หลังจากการเรียงลำดับอาร์เรย์เสร็จสิ้นให้เขียนกลับไปที่รายการ listiterator <t> i = list.listiterator (); สำหรับ (int j = 0; j <t.length; j ++) {i.next (); i.set ((t) t [j]); }} // เนื่องจากไม่สามารถใช้ยาสามัญใน Java, ชนิดข้อมูลดั้งเดิม (int, double, byte, ฯลฯ ) คุณสามารถใช้กลไกการทำงานมากเกินไปเพื่อจัดเรียงอาร์เรย์ดั้งเดิมเหล่านี้ (int [], double [], byte [] ฯลฯ ) เพื่อที่จะแบ่งปันฟังก์ชั่นการเรียงลำดับเดียวกันกลไกดั้งเดิม (autoboxing, Unboxing) กลไกถูกนำมาใช้เพื่อห่อหุ้มมันลงในประเภทวัตถุที่สอดคล้องกันสร้างอาร์เรย์วัตถุใหม่เรียงลำดับแล้ว deencapsulate ข้อเสียของสิ่งนี้คือต้องใช้ขั้นตอนการแปลงเพิ่มเติมและพื้นที่เพิ่มเติมเพื่อบันทึกอาร์เรย์ที่ห่อหุ้ม อีกวิธีหนึ่งคือการคัดลอกรหัสการเรียงลำดับลงในแต่ละฟังก์ชั่นโอเวอร์โหลด ฟังก์ชั่นการเรียงลำดับ () ในคลาส java.util.arrays ใน API อย่างเป็นทางการใช้วิธีนี้ซึ่งสามารถมองเห็นได้จากซอร์สโค้ดของคลาสอาร์เรย์ การเรียงลำดับโมฆะสาธารณะคงที่ (int [] อินพุต) {จำนวนเต็ม [] t = จำนวนเต็มใหม่ [อินพุต. length]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; // encapsulation} quicksort (t, 0, t.length); // การเรียงลำดับ (int i = 0; i <อินพุต. อินพุต) {double [] t = ใหม่ double [input.length]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // ฟังก์ชั่นโอเวอร์โหลดของไบต์ [] อาร์เรย์การเรียงลำดับแบบคงที่สาธารณะ (ไบต์ [] อินพุต) {byte [] t = byte ใหม่ [input.length]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length); input.length; i ++) {อินพุต [i] = t [i]; }} // short [] ฟังก์ชั่นโอเวอร์โหลดโมฆะแบบคงที่สาธารณะ (อินพุตสั้น []) {short [] t = ใหม่สั้น [อินพุต. length]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // short [] ฟังก์ชั่นโอเวอร์โหลดโมฆะแบบคงที่สาธารณะ (char [] อินพุต) {อักขระ [] t = อักขระใหม่ [input.length]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // ฟังก์ชั่นการโอเวอร์โหลดของ float [] อาร์เรย์การเรียงลำดับโมฆะสาธารณะแบบคงที่ (อินพุต float []) {float [] t = ใหม่ลอย [อินพุตความยาว]; สำหรับ (int i = 0; i <input.length; i ++) {t [i] = อินพุต [i]; } Quicksort (t, 0, t.length); สำหรับ (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // ฟังก์ชั่นหลักสำหรับการทดสอบโมฆะคงที่สาธารณะหลัก (สตริง [] args) {// ผลิตอาร์เรย์ int [] ที่ประกอบด้วยตัวเลขสุ่มเพื่อทดสอบ int len = 10; int [] input = new int [len]; สุ่ม r = ใหม่สุ่ม (); System.out.print ("int [] ก่อนการเรียงลำดับ:"); สำหรับ (int i = 0; i <input.length; i ++) {input [i] = r.nextint (10*len); System.out.print (อินพุต [i] + ""); } system.out.println (); System.out.print ("int [] หลังจากการเรียงลำดับ:"); เรียงลำดับ (อินพุต); สำหรับ (int i: input) {system.out.print (i + ""); } system.out.println (); // สร้างอาร์เรย์ของสตริงเพื่อทดสอบสตริง [] s = สตริงใหม่ [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("String [] ก่อนการเรียงลำดับ:"); สำหรับ (int i = 0; i <s.length; i ++) {system.out.print (s [i]+""); } system.out.println (); System.out.print ("String [] หลังจากการเรียงลำดับ:"); เรียงลำดับ; สำหรับ (int i = 0; i <s.length; i ++) {system.out.print (s [i]+""); } system.out.println (); // สร้างรายการสตริงเพื่อทดสอบรายการ <String> l = ใหม่ LinkedList <String> (); S = สตริงใหม่ [] {"B", "A", "E", "D", "F", "C"}; System.out.print ("LinkedList <String> ก่อนการเรียงลำดับ:"); สำหรับ (int j = 0; j <s.length; j ++) {l.add (s [j]); System.out.print (s [j] + ""); } system.out.println (); เรียงลำดับ (l); System.out.print ("LinkedList <String> หลังจากการเรียงลำดับ:"); สำหรับ (สตริง ts: l) {system.out.print (ts + ""); } system.out.println (); -เรียกใช้การทดสอบฟังก์ชั่นหลักและจากผลลัพธ์คุณจะเห็นว่าคลาส Quicksort ทำงานตามปกติ:
int [] ก่อนการเรียงลำดับ: 65 48 92 26 3 8 59 21 16 45INT [] หลังจากการเรียงลำดับ: 3 8 16 21 26 45 48 59 65 92STRING [] ก่อนการเรียงลำดับ: BAEDFC String [] หลังจากการเรียงลำดับ: ABCDEF LINKEDLIST <String>