ภาพรวม
การเรียงลำดับอย่างรวดเร็วเป็นอัลกอริทึมการเรียงลำดับที่พัฒนาโดย Tony Hall ในสถานการณ์เฉลี่ยคำสั่งของรายการ n ต้องมีการเปรียบเทียบ (nlogn) ในความเป็นจริงการเรียงลำดับอย่างรวดเร็วมักจะเร็วกว่าอัลกอริธึมอื่น ๆ (Nlogn) อื่น ๆ เนื่องจากการวนรอบด้านในสามารถนำไปใช้ได้อย่างมีประสิทธิภาพในสถาปัตยกรรมส่วนใหญ่และในข้อมูลจริงส่วนใหญ่สามารถกำหนดทางเลือกของการออกแบบและลดความเป็นไปได้ของเงื่อนไขกำลังสองที่ต้องใช้เวลา
การเรียงลำดับอย่างรวดเร็วแบ่งบันทึกที่จะจัดเรียงเป็นสองส่วนอิสระผ่านคำสั่งหนึ่งซึ่งคำหลักของบางระเบียนมีขนาดเล็กกว่าคำหลักของส่วนอื่น ๆ จากนั้นทั้งสองบันทึกจะถูกจัดเรียงแยกต่างหากเพื่อให้บรรลุวัตถุประสงค์ในการสั่งซื้อทั้งหมด
ภาพประกอบภาพ:
ขั้นตอน
เมื่อเลือกองค์ประกอบเบนช์มาร์กองค์ประกอบแรกหรือองค์ประกอบสุดท้ายมักจะถูกเลือกเพื่อแบ่งบันทึกที่จะจัดเรียงเป็นสองส่วนอิสระผ่านการเรียงลำดับเดียวโดยที่ค่าองค์ประกอบของบางระเบียนมีขนาดเล็กกว่าค่าองค์ประกอบเบนช์มาร์ก องค์ประกอบที่บันทึกไว้ในส่วนอื่นมีขนาดใหญ่กว่าค่าอ้างอิง ในเวลานี้องค์ประกอบการอ้างอิงอยู่ในตำแหน่งที่ถูกต้องหลังจากเรียงลำดับแล้วทั้งสองส่วนของบันทึกจะยังคงจัดเรียงในลักษณะเดียวกันจนกว่าจะสั่งลำดับทั้งหมด
ตัวอย่าง
ข้อมูลดิบ:
3 5 2 6 2
เลือก 3 เป็นเกณฑ์มาตรฐาน
รอบแรก
จากขวาไปซ้ายเพื่อค้นหาสิ่งที่เล็กกว่า 3, 2 การแข่งขันและปรับ 2 และ 3 2 5 2 6 3 ครั้งหนึ่งครั้งและทิศทางของการค้นหากลับด้านจากซ้ายไปขวาเพื่อหาสิ่งที่ใหญ่กว่า 3, 5 การแข่งขันและปรับ 2 3 2 6 5 จากขวาไปซ้ายเพื่อค้นหาสิ่งที่เล็กกว่า 3, 2
รอบ 2
วิธีเดียวกับข้างต้นดำเนินการสำหรับ [2 2] และ 2 2 3 6 5 5
รอบที่สาม
วิธีเดียวกับข้างต้นดำเนินการสำหรับ [6 5] และ 2 2 3 5 6 6
ผลลัพธ์สุดท้าย
2 2 3 5 6
การใช้งานรหัส (Java)
แพ็คเกจ com.coder4j.main.arithmetic.sorting; คลาสสาธารณะอย่างรวดเร็ว {private static int mark = 0; / ** * วิธีการแลกเปลี่ยนเสริม * * @param array * @param a * @param b */ การแลกเปลี่ยนโมฆะแบบคงที่ส่วนตัว (int [] อาร์เรย์, int a, int b) {ถ้า (a! = b) {int temp = array [a]; อาร์เรย์ [a] = อาร์เรย์ [b]; อาร์เรย์ [b] = อุณหภูมิ; // ค้นหาการจับคู่, switch system.out.println ("shift" + array [a] + "และ" + array [b] + ", get"); สำหรับ (int i: array) {system.out.print (i + ""); } system.out.println (); }} / ** * รอบใหม่ของการแยก * * @param array * @param low * @param สูง * @return * / พาร์ติชัน int คงที่ส่วนตัว (int array [], int ต่ำ, int สูง) {int base = array [ต่ำ]; Mark ++; System.out.println ("Throwth in Progress" + Mark + "การแยกล้อ, พื้นที่:" + ต่ำ + "-" + สูง); ในขณะที่ (ต่ำ <สูง) {ในขณะที่ (ต่ำ <high && array [สูง]> = base) {สูง-; System.out.println ("จากขวาไปซ้ายเพื่อค้นหาอัตราส่วน" + base + "ขนาดเล็กการเปลี่ยนแปลงตัวชี้:" + low + "-" สูง); } swap (อาร์เรย์, ต่ำ, สูง); ในขณะที่ (ต่ำ <high && array [ต่ำ] <= base) {low ++; System.out.println ("จากซ้ายไปขวาเพื่อค้นหาอัตราส่วน" + base + "ขนาดใหญ่ตัวชี้เปลี่ยน:" + ต่ำ + "-" สูง); } swap (อาร์เรย์, ต่ำ, สูง); } return low; } / ** * การเรียงลำดับอย่างรวดเร็วของอาร์เรย์โทรซ้ำ * * @param array * @param ต่ำ * @param ความสูง * @return * / ส่วนตัวคงที่ int [] quicksort (int [] อาร์เรย์, int ต่ำ, ความสูง int) {ถ้า (ต่ำสุด) Quicksort (Array, Low, Division - 1); Quicksort (Array, Division + 1, ความสูง); } return array; } / ** * เรียงลำดับอย่างรวดเร็ว * * @param array * @return * / public Static int [] sort (int [] array) {return Quicksort (array, 0, array.length - 1); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (อาร์เรย์); System.out.println ("ผลลัพธ์สุดท้าย"); สำหรับ (int i: เรียงลำดับ) {system.out.print (i + ""); -ผลการทดสอบผลลัพธ์:
เลือกทั้งหมดและใส่ไว้ในหมายเหตุ รอบแรกของการแยกกำลังดำเนินการ พื้นที่: 0-4 รอบที่สองของการปรับคือ 2 และ 3 รอบที่สองของการแยกคือ 2 5 2 6 3 รอบที่สองของการแยกคือ 3 และ 5 รอบที่สองของการแยกคือ 2 3 2 6 5 รอบที่สองของการแยกคือ 3 และ 5 รอบที่สองของการแยก 2 และ 3 รอบที่สองและการแยกรอบที่สอง การแยกคือ 2 และ 3 รอบที่สองของการแยกคือ 2 และ 3 รอบที่สองของการแยกคือ 2 และ 3 รอบที่สองของการแยกคือ 2 และ 2 คือ 3. 6. รอบที่สามของการแยกคือ 2 คือ 2 และ 3 คือ 6 รอบที่สองของการแยก 2 คือ 2 คือ 2 และ 3 คือ 2 5. รอบสุดท้ายของการแยกคือ 2 คือ 2 และ 3 คือ 5 ผลลัพธ์สุดท้ายคือ 2 คือ 2 และ 3 คือ 5 6. ผลลัพธ์สุดท้ายคือ 2 2 3 5. 6.
หลังจากการทดสอบมันสอดคล้องกับผลลัพธ์ในตัวอย่าง