การเรียงลำดับอย่างรวดเร็วถูกนำมาใช้กันอย่างแพร่หลายในฐานะอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพ วิธี Arrays.sort ใน JDK ของ SUN ใช้การเรียงลำดับอย่างรวดเร็ว
Quick Sort ใช้แนวคิดการแบ่งแยกและพิชิตแบบคลาสสิก:
แบ่ง: เลือก X ดั้งเดิม (โดยปกติจะเป็นองค์ประกอบแรกของอาร์เรย์) และแบ่งอาร์เรย์ออกเป็น สองส่วนผ่านการดำเนินการแบ่งพาร์ติชัน: ครึ่งซ้ายน้อยกว่าหรือเท่ากับ X และครึ่งขวามากกว่าหรือเท่ากับ X .
พิชิต: อาร์เรย์ย่อยด้านซ้ายและขวาเรียกกระบวนการแบ่งซ้ำ
รวม: การเรียงลำดับด่วนถูกใช้เป็นอัลกอริทึมการเรียงลำดับแบบแทนที่ และไม่จำเป็นต้องดำเนินการผสานใดๆ
จะเห็นได้ว่าส่วนหลักของการเรียงลำดับอย่างรวดเร็วคือกระบวนการแบ่งพาร์ติชัน ต่อไปนี้เป็นตัวอย่างเพื่ออธิบายรายละเอียดวิธีการแบ่งพาร์ติชันอาร์เรย์ (ภาพที่นำมาจาก "Introduction to Algorithms")
การเริ่มต้น: เลือกดั้งเดิม P=2 ซึ่งเป็นองค์ประกอบแรกของอาร์เรย์ i=1,j=i+1=2 (ตัวห้อยอาร์เรย์เริ่มต้นด้วย 1)
ค่าคงที่ของลูป: องค์ประกอบระหว่าง 2~i ทั้งหมดน้อยกว่าหรือเท่ากับ P และองค์ประกอบระหว่าง i+1~j ล้วนมากกว่าหรือเท่ากับ P
กระบวนการวนซ้ำ: j เปลี่ยนจาก 2 ถึง n ตรวจสอบองค์ประกอบที่ตำแหน่ง j และหากมากกว่าหรือเท่ากับ P ให้วนซ้ำต่อไป หากน้อยกว่า P ให้สลับองค์ประกอบที่ตำแหน่ง j (ซึ่งไม่ควรปรากฏในช่วง i+1~j) กับองค์ประกอบที่ตำแหน่ง i+1 (ยังอยู่ในช่วง i+1~j หลังการแลกเปลี่ยน) และในเวลาเดียวกันก็เปลี่ยน i+1 ซึ่งจะรักษาค่าคงที่ของลูป (ดูคำอธิบายของค่าคงที่ของลูปด้านบน) จนกระทั่ง j=n การดำเนินการวนรอบสุดท้ายจะเสร็จสมบูรณ์
ควรสังเกตว่าหลังจากเสร็จสิ้นการวนซ้ำ องค์ประกอบที่ตำแหน่ง i จะต้องถูกแลกเปลี่ยนกับองค์ประกอบแรกของอาเรย์เพื่อให้เป็นไปตามข้อกำหนดที่เราตั้งไว้ครั้งแรก (สอดคล้องกับขั้นตอน i-th ในรูป)
ผู้อ่านที่ระมัดระวังอาจนึกถึงวิธีการแบ่งพาร์ติชั่นที่ตรงไปตรงมามากกว่า นั่นคือการนำเอาค่าดั้งเดิมออกและเก็บไว้ในอาร์เรย์อื่นที่มีขนาดเท่ากัน เมื่อเผชิญหน้าองค์ประกอบที่เล็กกว่าแบบดั้งเดิม องค์ประกอบเหล่านั้นจะถูกจัดเก็บไว้ในครึ่งซ้ายของอาร์เรย์ องค์ประกอบที่มีขนาดใหญ่กว่าแบบดั้งเดิมจะถูกเก็บไว้ในครึ่งซ้ายของอาร์เรย์ ความซับซ้อนของการดำเนินการดังกล่าวก็เป็นเชิงเส้นเช่นกัน กล่าวคือ Theta(n) แต่ความซับซ้อนของพื้นที่ก็เพิ่มขึ้นเป็นสองเท่า นี่เป็นข้อดีของการเรียงลำดับอย่างรวดเร็ว
คัดลอกรหัสรหัส ดังต่อไปนี้:
QuickSort คลาสสาธารณะ {
โมฆะส่วนตัว QuickSort (อาร์เรย์ int [], int start, int end)
-
ถ้า(เริ่มต้น<สิ้นสุด)
-
int key=array[start];//เริ่มต้นและบันทึกข้อมูลพื้นฐาน
int i=start,j;//เริ่มต้น i,j
สำหรับ(j=เริ่มต้น+1;j<=สิ้นสุด;j++)
if(array[j]<key)//หากองค์ประกอบนี้น้อยกว่าค่าดั้งเดิม ให้แลกเปลี่ยนองค์ประกอบนี้กับองค์ประกอบที่ i+1 และเพิ่ม 1 ไปที่ i หากมากกว่าหรือเท่ากับค่าดั้งเดิม ให้ดำเนินการต่อ ห่วง
-
int temp=อาร์เรย์[เจ];
อาร์เรย์[j]=อาร์เรย์[i+1];
อาร์เรย์[i+1]=อุณหภูมิ;
ฉัน++;
-
-
array[start]=array[i];//แลกเปลี่ยนองค์ประกอบและพื้นฐานที่ i
อาร์เรย์ [i] = คีย์;
QuickSort(array, start, i-1);//เรียกซ้ำ
QuickSort(อาร์เรย์, i+1, สิ้นสุด);
-
-
โมฆะสาธารณะคง main (String [] args)
-
int[] array=ใหม่ int[]{11,213,134,44,77,78,23,43};
QuickSort(อาร์เรย์, 0, array.length-1);
สำหรับ(int i=0;i<array.length;i++)
-
System.out.println((i+1)+"th:"+array[i]);
-
-
-