การเรียงลำดับอย่างรวดเร็วคือการเรียงลำดับของการแลกเปลี่ยนการแลกเปลี่ยนที่เสนอโดย Crahoare ในปี 1962 แนวคิดพื้นฐานของวิธีนี้คือ:
1. ก่อนอื่นใช้หมายเลขจากลำดับเป็นหมายเลขอ้างอิง
2. ในกระบวนการแบ่งพาร์ติชันให้ใส่ตัวเลขทั้งหมดที่ใหญ่กว่าตัวเลขนี้ไปทางขวาและตัวเลขทั้งหมดเล็กกว่าหรือเท่ากับด้านซ้าย
3. ทำซ้ำขั้นตอนที่สองสำหรับช่วงเวลาซ้ายและขวาจนกว่าจะมีเพียงตัวเลขเดียวในแต่ละช่วงเวลา
อัลกอริทึมมีความคิดที่ชัดเจน แต่ถ้าค่าขอบเขตไม่ได้รับการจัดการที่ดีในระหว่างกระบวนการแบ่งช่วงเวลามันเป็นเรื่องง่ายที่จะทำให้เกิดข้อบกพร่อง ต่อไปนี้เป็นสองความคิดที่ชัดเจนยิ่งขึ้นเพื่อเป็นแนวทางในการเขียนรหัสการแบ่งช่วงเวลา
การคิดประเภทแรกคือวิธีการขุดหลุมที่เรียกว่าการคิด ต่อไปนี้คือการวิเคราะห์กระบวนการขุดหลุมโดยการวิเคราะห์ตัวอย่าง:
การใช้อาร์เรย์เป็นตัวอย่างให้ใช้หมายเลขแรกในช่วงเวลาเป็นหมายเลขอ้างอิง
เริ่มแรกซ้าย = 0; ขวา = 9; x = a [ซ้าย] = 72
เนื่องจากหมายเลขใน [0] ได้รับการบันทึกไปยัง X จึงสามารถเข้าใจได้ว่าเป็นการขุดหลุมในอาร์เรย์ A [0] และข้อมูลอื่น ๆ สามารถกรอกข้อมูลได้ที่นี่
เริ่มต้นจากขวาและมองหาจำนวน <= x เห็นได้ชัดว่าเมื่อถูกต้อง = 8 หากเป็นไปตามเงื่อนไขให้ขุด [8] และเติมลงในหลุมก่อนหน้า A [ซ้าย] หลุม A [0] ได้รับการแก้ไข แต่มีหลุมใหม่ A [8] เกิดขึ้น ฉันควรทำอย่างไร? ง่ายค้นหาหมายเลขเพื่อเติมเต็มในหลุม A [8] เวลานี้เริ่มจากซ้ายและค้นหาตัวเลขที่มากกว่า X เมื่อซ้าย = 3 ตรงตามเงื่อนไขขุด [3] และเติมในหลุมก่อนหน้า A [ขวา];
อาร์เรย์กลายเป็น:
ทำซ้ำขั้นตอนข้างต้นและอาร์เรย์สุดท้ายจะกลายเป็นแบบฟอร์มต่อไปนี้:
จะเห็นได้ว่าตัวเลขก่อน [5] มีขนาดเล็กกว่าและตัวเลขหลังจาก [5] มีขนาดใหญ่กว่ามัน เติม x ลงในหลุมของ [5] และข้อมูลจะกลายเป็น:
ดังนั้นให้ทำซ้ำขั้นตอนข้างต้นสำหรับสองช่วงย่อย A [0 … 4] และ A [6 … 9]
สรุปจำนวนหลุมขุด
1. i = l; j = r; ขุดหมายเลขอ้างอิงเพื่อสร้างหลุมแรก A [i]
2. j-จากด้านหลังไปด้านหน้าค้นหาหมายเลขที่เล็กกว่านั้นขุดหมายเลขนี้และเติมเต็มหลุมก่อนหน้า a [i]
3. i ++ พบตัวเลขที่ใหญ่กว่าจากด้านหน้าไปด้านหลังและหลังจากพบแล้วให้ขุดตัวเลขนี้แล้วเติมลงในหลุมก่อนหน้า A [J]
4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่าฉัน == j และกรอกหมายเลขอ้างอิงลงใน [i]
ทำตามวิธีการพาร์ติชันนี้รหัส Java จะถูกจัดเรียงอย่างรวดเร็วดังนี้:
พาร์ติชันคลาสสาธารณะ { / ** * ขึ้นอยู่กับการแบ่งฐานอันเล็ก ๆ อยู่ทางซ้ายและอันที่มีขนาดใหญ่อยู่ทางขวาและไม่จำเป็นต้องสั่งลำดับทั้งหมด * * @param ary * @param base * / การเรียงลำดับโมฆะคงที่ (int [] ary, int base) int right = ary.length - 1; int leftpoint = ซ้าย, rightpoint = ขวา; ในขณะที่ (จริง) {// แบ่งออกเป็นซ้ายและขวาไปขวาในเวลาเดียวกันเพื่อเปรียบเทียบจากซ้ายไปขวาในขณะที่ (leftpoint <right && ary [leftpoint ++] <base); // leftpoint มากกว่าขวาหรือ ary [leftpoint]> ฐานหยุดการวนซ้ำในขณะที่ (rightpoint> = ซ้าย && ary [rightpoint-]> ฐาน); // บน System.out.println ("ดัชนีที่ต้องเปลี่ยนทางด้านซ้าย:" + (leftpoint-1)); System.out.println ("ดัชนีที่ต้องเปลี่ยนทางด้านขวา:"+ (RightPoint+ 1)); // ดัชนีทั้งสองที่ไม่ตรงตามเงื่อนไขที่ได้รับข้างต้นนั่นคือดัชนีสองตัวที่ต้องเปลี่ยนถ้า (leftpoint - 1 <rightpoint + 1) {// swap (ary, leftpoint - 1, rightpoint + 1); util.printarray (ARY); leftpoint = ซ้าย; RightPoint = ขวา; } else {break; }}} การแลกเปลี่ยนโมฆะแบบคงที่ส่วนตัว (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = อุณหภูมิ; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] ary = util.generateintarray (10); System.out.println ("ลำดับต้นฉบับ:"); util.printarray (ARY); เรียงลำดับ (ary, 5); System.out.println ("เรียงลำดับ:"); util.printarray (ARY); - ผลลัพธ์:
ลำดับต้นฉบับ: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] ดัชนีเพื่อแลกเปลี่ยนทางด้านซ้าย: 1 ดัชนีเพื่อแลกเปลี่ยนทางด้านขวา: 8 [2, 0, 4, 3, 7, 5, 1, 9, 8, 6] ดัชนีการแลกเปลี่ยนทางซ้าย: 4 ดัชนีเพื่อแลกเปลี่ยนทางด้านขวา การเรียงลำดับ: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
ความคิดแนวทางอื่นของการแบ่งช่วงเวลา:
ใช้องค์ประกอบแรกของอาร์เรย์เป็นค่าช่วงเวลาพาร์ติชันจากองค์ประกอบที่สองจนกระทั่งผลลัพธ์ที่แสดงในรูปที่เกิดขึ้น
จากนั้นแลกเปลี่ยนค่าขอบเขตที่ถูกต้องและ t ของช่วงเวลา l <t เพื่อสร้างผลลัพธ์ต่อไปนี้:
ด้วยวิธีนี้คุณสามารถเขียนรหัสการเรียงลำดับอย่างรวดเร็วดังนี้:
โมฆะสาธารณะ QSort (int array [], int ซ้าย, int ขวา) {ถ้า (ซ้าย <ขวา) {int key = array [ซ้าย]; int สูง = ขวา; int ต่ำ = ซ้าย+1; ในขณะที่ (จริง) {ในขณะที่ (ต่ำ <= สูง && อาร์เรย์ [ต่ำ] <= คีย์) ต่ำ ++; ในขณะที่ (ต่ำ <= สูง && อาร์เรย์ [สูง]> = คีย์) สูง-; ถ้า (ต่ำ> สูง) แตก; สลับ (อาร์เรย์, ต่ำ, สูง); } swap (อาร์เรย์, ซ้าย, สูง); printarray (อาร์เรย์); QSORT (อาร์เรย์, ซ้าย, สูง -1); QSORT (อาร์เรย์, สูง+1, ขวา); -