เมื่อเทียบกับอัลกอริทึมเช่นการเรียงลำดับฟองการเรียงลำดับการเลือก ฯลฯ หลักการอัลกอริทึมเฉพาะและการใช้งานการเรียงลำดับอย่างรวดเร็วนั้นยาก เพื่อให้เข้าใจการเรียงลำดับอย่างรวดเร็วได้ดีขึ้นเรายังคงอธิบายหลักการอัลกอริทึมของการเรียงลำดับอย่างรวดเร็วในรูปแบบของตัวอย่าง ในอัลกอริทึมการเรียงลำดับก่อนหน้านี้เราจะใช้ปัญหาการเรียงลำดับความสูงของนักกีฬา 5 คนเป็นตัวอย่างในการอธิบาย เพื่อให้สะท้อนถึงลักษณะของการเรียงลำดับที่รวดเร็วเราจะเพิ่มนักกีฬาอีก 3 คนที่นี่ นักกีฬา 8 คนและข้อมูลความสูงของพวกเขาในตัวอย่างมีดังนี้ (f, g, h เป็นนักกีฬาใหม่): a (181), b (169), c (187), d (172), E (163), F (191), G (189), H (182)
ในอัลกอริทึมการเรียงลำดับก่อนหน้าการเรียงลำดับเหล่านี้ทั้งหมดทำโดยโค้ช ตอนนี้จำนวนนักกีฬาเพิ่มขึ้นโค้ชก็ต้องการที่จะหยุดพักดังนั้นโค้ชเรียกผู้ช่วยสองคนและขอให้ผู้ช่วยทั้งสองจัดเรียงความสูงของนักกีฬา 8 คนจากซ้ายไปขวาและต่ำไปสูงในการเรียงลำดับอย่างรวดเร็ว
ตามหลักการอัลกอริทึมของวิธีการเรียงลำดับอย่างรวดเร็วผู้ช่วยทั้งสองยืนอยู่ทั้งสองด้านของการจัดเรียงของนักกีฬาดังที่แสดงในรูปด้านล่าง:
ขั้นแรกผู้ช่วย 1 เลือกนักกีฬาจากการจัดเรียง (โดยปกติจะเลือกนักกีฬาคนแรกทางซ้ายหรือนักกีฬากลาง) และที่นี่เลือกนักกีฬา A (181) เนื่องจากการเรียงลำดับมาจากซ้ายไปขวาและจากต่ำถึงสูงผู้ช่วย 1 ต้องมีนักกีฬาที่มีความสูงน้อยกว่า (181) (ที่เลือก A (181) ถูกใช้เป็นเกณฑ์มาตรฐานสำหรับการเปรียบเทียบการเปรียบเทียบทั้งหมดในรอบนี้จะถูกเปรียบเทียบ
มาอ้างอิงถึงไดอะแกรมโดยละเอียดของรอบแรกของการเรียงลำดับอย่างรวดเร็ว
เมื่อผู้ช่วยทั้งสองพบกันในระหว่างการเรียงลำดับและกระบวนการค้นหาการเปรียบเทียบรอบปัจจุบันจะหยุดลงและนักกีฬาที่เลือก A (181) จะถูกวางไว้ในพื้นที่ว่างที่ผู้ช่วยทั้งสองมาพบกัน:
ในการเรียงลำดับอย่างรวดเร็วการเรียงลำดับรอบนี้จะสิ้นสุดลงเมื่อผู้ช่วยสองคนพบกัน ในเวลานี้เราพบว่าการใช้ตำแหน่ง A (181) ที่นักกีฬาสองคนพบกันเป็นจุดดิวิชั่นคนทางด้านซ้ายคือนักกีฬาที่มีขนาดเล็กกว่า (181) และคนที่อยู่ทางด้านขวาคือนักกีฬาที่มีขนาดใหญ่กว่า (181) ในเวลานี้เราจะแยกสองประเภททางด้านซ้ายและขวาของ A (181) หากเรายังคงเรียงลำดับการเตรียมการทั้งสองด้านโดยใช้วิธีการเรียงลำดับของผู้ช่วยทั้งสองข้างต้นหลังจากการเตรียมการหลายครั้งในที่สุดเราก็จะได้รับผลลัพธ์การเรียงลำดับที่เราต้องการ
ข้างต้นคือกระบวนการติดตั้งการเรียงลำดับทั้งหมดของการเรียงลำดับอย่างรวดเร็ว การเรียงลำดับอย่างรวดเร็วคือการใช้กฎการเรียงลำดับข้างต้นเพื่อแบ่งการจัดเรียงออกเป็นสองข้อและการเตรียมการทั้งสองเป็นการเตรียมการสี่ครั้งจนกว่าจะไม่มีข้อตกลงที่จะแบ่งและในที่สุดเราก็ได้รับผลการเรียงลำดับที่เราต้องการ
ตอนนี้เรายังคงตั้งโปรแกรมรหัส Java เพื่อเรียงลำดับความสูงของนักกีฬา 8 คนข้างต้นโดยใช้การเรียงลำดับอย่างรวดเร็ว:
/*** การเรียงลำดับอย่างรวดเร็วขององค์ประกอบในอาร์เรย์ที่ระบุตั้งแต่ต้นจนจบ** @param อาร์เรย์อาร์เรย์ที่ระบุ* @param เริ่มต้นจุดที่เกิดขึ้นของการสอบถามอาเรย์ที่ต้องจัดเรียงอย่างรวดเร็ว* @param สิ้นสุดดัชนีอาร์เรย์ที่ต้องจัดเรียงอย่างรวดเร็ว เทียบเท่ากับตำแหน่งของผู้ช่วย 2 int i = start, j = end; int pivot = array [i]; // ใช้องค์ประกอบแรกเป็นองค์ประกอบอ้างอิง intextindex = i; // ดัชนีตำแหน่งของพื้นที่ว่างถูกระบุและค่าเริ่มต้นคือตำแหน่งขององค์ประกอบอ้างอิงที่ถูกเรียกคืน // หากมีมากกว่า 1 องค์ประกอบที่จะจัดเรียงให้ป้อนการเรียงลำดับด่วน (ตราบใดที่ฉันและ j แตกต่างกันหมายความว่าองค์ประกอบอาร์เรย์อย่างน้อย 2 ต้องเรียงลำดับ < ถ้า (i <j) {// ถ้าผู้ช่วย 2 ค้นหาองค์ประกอบที่เกี่ยวข้องก่อนที่จะพบผู้ช่วย 1 มันจะให้องค์ประกอบกับ "ตำแหน่งว่าง" ของผู้ช่วย 1, J กลายเป็นอาร์เรย์อาร์เรย์ว่างเปล่า } // ผู้ช่วย 1 เริ่มมองหาองค์ประกอบที่ใหญ่กว่าองค์ประกอบอ้างอิงจากซ้ายไปขวา (i <j && array [i] <= pivot) i ++; ถ้า (i <j) {// ถ้าผู้ช่วย 1 ค้นหาองค์ประกอบที่เกี่ยวข้องก่อนที่จะพบผู้ช่วย 2 มันจะให้องค์ประกอบกับ "ตำแหน่งงานว่าง" ของผู้ช่วย 2 และฉันกลายเป็นอาร์เรย์ว่าง }} // หลังจากผู้ช่วย 1 และผู้ช่วย 2 พบลูปจะหยุดและค่าอ้างอิงเริ่มต้นจะถูกนำไปยังอาร์เรย์ว่างสุดท้าย [emportIndex] = pivot; // ===== การเรียงลำดับอย่างรวดเร็วรอบนี้เสร็จสมบูรณ์ ====== // หากมีมากกว่า 2 องค์ประกอบที่ด้านซ้ายของจุดแยก i การโทรแบบเรียกซ้ำจะยังคงเรียงลำดับอย่างรวดเร็วหาก (i - start> 1) {Quicksort (Array, 0, i - 1); } // หากมีมากกว่า 2 องค์ประกอบทางด้านขวาของจุดแยก j การโทรแบบเรียกซ้ำจะยังคงเรียงลำดับอย่างรวดเร็วหาก (สิ้นสุด - j> 1) {quicksort (อาร์เรย์, j + 1, สิ้นสุด); }} // วิธีการหลักโมฆะสาธารณะคงที่หลัก (สตริง [] args) {// ===== เรียงลำดับจากต่ำถึงสูงโดยใช้วิธีการเรียงลำดับอย่างรวดเร็วเพื่อแสดงถึงความสูงของ 8 นักกีฬา ====== // a (181), B (169), C (187), D (172), E (163) 187, 172, 163, 191, 189, 182}; // เรียกวิธีการเรียงลำดับอย่างรวดเร็ว Quicksort (ความสูง, 0, heights.length - 1); // ผลลัพธ์การจัดเรียงเอาต์พุตสำหรับ (ความสูง int: ความสูง) {system.out.println (ความสูง); -ผลลัพธ์การเรียกใช้รหัส Java ด้านบนเป็นเอาต์พุตดังนี้:
163169172181182187189191
หมายเหตุ: เนื่องจากความแตกต่างในการคิดในท้องถิ่นอาจมีหลายรูปแบบในการใช้รหัสการเรียงลำดับอย่างรวดเร็วข้างต้น อย่างไรก็ตามไม่ว่าตัวแปรจะเป็นอะไรแนวคิดหลักของการเรียงลำดับอย่างรวดเร็วจะไม่เปลี่ยนแปลง
การดำเนินการอื่น: การสแกนทางเดียว
มีเวอร์ชันสแกนทางเดียวสำหรับการแยกอาร์เรย์อย่างรวดเร็ว ขั้นตอนที่เฉพาะเจาะจงคือการเลือกองค์ประกอบสุดท้ายในอาร์เรย์เป็นองค์ประกอบการหั่นและตั้งสองพอยน์เตอร์ ตัวชี้ฉันชี้ไปที่ตำแหน่งด้านหน้าขององค์ประกอบแรกในอาร์เรย์และ J ชี้ไปที่องค์ประกอบแรกในอาร์เรย์ J สแกนจากด้านหน้าไปขวาและขวา เมื่อพบองค์ประกอบการหั่นน้อยกว่าหรือเท่ากับให้เพิ่มฉันลงในหนึ่งแล้วแลกเปลี่ยนองค์ประกอบที่ชี้ไปที่ I และ J ในที่สุดแลกเปลี่ยนองค์ประกอบที่ตำแหน่ง I+1 และองค์ประกอบการหั่นเพื่อให้เสร็จสิ้นแผนกอาร์เรย์ การใช้งานรหัสมีดังนี้:
พาร์ติชัน int (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; ในขณะที่ (j <hi) {ถ้า (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hi); ส่งคืน i + 1;}