หลักการ Java Quicksort และรหัสการใช้งาน

Quicksort เป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพมากขึ้นและมีประสิทธิภาพมากขึ้นและมักถูกกล่าวถึงในระหว่างกระบวนการสัมภาษณ์ มาอธิบายหลักการของมันโดยละเอียดและให้การใช้งานเวอร์ชัน Java

แนวคิดการเรียงลำดับด่วน:

สองส่วนอิสระถูกหารด้วยการเรียงลำดับองค์ประกอบข้อมูล RN ในการเดินทางครั้งเดียว ส่วนหนึ่งของคำหลักมีขนาดเล็กกว่าส่วนอื่น ๆ จากนั้นเรียงลำดับคำหลักของทั้งสองส่วนทีละหนึ่งจนกว่าจะมีองค์ประกอบอิสระเพียงอย่างเดียวและคอลเลกชันองค์ประกอบทั้งหมดเป็นไปตามลำดับ

กระบวนการจัดเรียงอย่างรวดเร็ว - วิธีการขุดหลุมและหมายเลขเติม (นี่คือชื่อที่สดใสมาก) สำหรับชุดองค์ประกอบ R [ต่ำ ... สูง] ก่อนอื่นใช้ตัวเลข (โดยปกติจะเป็น R [ต่ำ]) เป็นข้อมูลอ้างอิง และ r [ต่ำ] จัดเรียงองค์ประกอบทั้งหมดเป็นมาตรฐาน

ทั้งหมดที่มีขนาดเล็กกว่า r [ต่ำ] ถูกวางไว้ด้านหน้าทั้งหมดที่มีขนาดใหญ่กว่า r [ต่ำ] จะถูกวางไว้ที่ด้านหลังและจากนั้น R [ต่ำ] จะถูกใช้เป็นขอบเขตและ R [ต่ำ ... สูง] คือ แบ่งออกเป็นสองชุดย่อยแล้วแบ่งออก จนต่ำ> = สูง

ตัวอย่างเช่น: กระบวนการดำเนินการเรียงลำดับอย่างรวดเร็วของ r = {37, 40, 38, 42, 461, 5, 7, 9, 12} มีดังนี้ (หมายเหตุ: ตารางองค์ประกอบต่อไปนี้ที่อธิบายไว้ด้านล่างเริ่มต้นจาก 0):

เริ่มเลือกฐานฐาน = 37 ตารางด้านล่างต่ำ = 0, สูง = 8 เริ่มต้นจากสูง = 8 ถ้า r [8] <ฐานเขียนเนื้อหาในตำแหน่งสูงลงใน R [ต่ำ] และสูง ตำแหน่งว่างเปล่าต่ำ = ต่ำ +1;

เริ่มต้นการตรวจสอบจากต่ำเนื่องจากต่ำ = 1, r [ต่ำ]> ฐานเขียน r [ต่ำ] ถึง r [สูง], สูง = สูง -1;

ตรวจพบต่ำ <สูงดังนั้นการเรียงลำดับอย่างรวดเร็วครั้งแรกยังคงต้องดำเนินการต่อ:

ในเวลานี้ต่ำ = 1, สูง = 7, เพราะ r [สูง] <ฐาน, r [สูง] ถูกเขียนลงใน r [ต่ำ], ต่ำ = ต่ำ + 1;

เริ่มการตรวจจับจากต่ำ, ต่ำ = 2, r [ต่ำ]> ฐานดังนั้น r [ต่ำ] เขียนถึง r [สูง], สูง = สูง -1;

ตรวจพบต่ำน้อยกว่าสูงกว่า

ในเวลานี้ต่ำ = 2, สูง = 6, ในทำนองเดียวกัน, r [สูง] <ฐาน, เขียน r [สูง] ถึง r [ต่ำ], ต่ำ = ต่ำ+1;

ตรวจจับต่อจากต่ำ, ต่ำ = 3, สูง = 6, r [ต่ำ]> ฐานเขียน r [ต่ำ] ถึง r [สูง], สูง = สูง -1;

ตรวจพบต่อไปว่าต่ำน้อยกว่าสูง

ในเวลานี้ต่ำ = 3, สูง = 5, ในทำนองเดียวกัน, r [สูง] <ฐาน, เขียน r [สูง] ลงใน r [ต่ำ], ต่ำ = ต่ำ +1;

ตรวจสอบต่อจากต่ำ, ต่ำ = 4, สูง = 5, เพราะ r [ต่ำ]> ฐานเขียน r [ต่ำ] ลงใน r [สูง], สูง = สูง -1;

ในเวลานี้มีการตรวจพบต่ำ == สูง == 4 ตำแหน่งนี้เป็นตำแหน่งที่ฐานอยู่และฐานถูกเขียนไปยังตำแหน่งนี้

จากนั้นทำการจัดเรียงลำดับอย่างรวดเร็ว rs1 = {12,9,7,5} และ rs2 = {461,42,38,40} จนกว่าจะมีองค์ประกอบเดียวใน RSI หรือไม่มีองค์ประกอบ

(หมายเหตุ: ในรูปแบบข้างต้นคุณจะเห็นว่ามีข้อมูลที่ซ้ำกันในการเรียงลำดับ (ไม่มีข้อมูลซ้ำในข้อมูลต้นฉบับ) นี่เป็นเพราะข้อมูลในตำแหน่งนั้นไม่ได้ถูกล้างเราจะดูข้อมูลของหน่วยความจำ บล็อกในเวลาที่กำหนด

การจัดเรียง Java อย่างรวดเร็ว:

การคัดลอกรหัสมีดังนี้:

บูลีนคงที่ส่วนตัว isempty (int [] n) {

ส่งคืน n == null ||

-

// //////////////////////////////////////////////// ///

-

* แนวคิดอัลกอริทึมการเรียงลำดับด่วน - วิธีการขุดหลุมและการเติม:

-

* @param n อาร์เรย์ที่จะจัดเรียง

-

public static void Quicksort (int [] n) {

ถ้า (isempty (n))

กลับ;

Quicksort (n, 0, n.length - 1);

-

void public public Void Quicksort (int [] n, int l, int h) {

ถ้า (isempty (n))

กลับ;

ถ้า (l <h) {

int pivot = พาร์ติชัน (n, l, h);

Quicksort (N, L, Pivot - 1);

Quicksort (n, pivot + 1, h);

-

-

พาร์ติชัน int คงที่ส่วนตัว (int [] n, int start, int end) {

int tmp = n [เริ่ม];

ในขณะที่ (start <end) {

ในขณะที่ (n [end]> = tmp && start <end)

จบ--;

if (start <end) {

n [start ++] = n [end];

-

ในขณะที่ (n [start] <tmp && start <end)

เริ่ม ++;

if (start <end) {

n [end--] = n [เริ่ม];

-

-

n [start] = tmp;

เริ่มต้นกลับ;

-

มีฟังก์ชั่นเช่นนี้ในรหัส:

การคัดลอกรหัสมีดังนี้:

Public Static Void Quicksortswap (int [] n, int l, int h)

ฟังก์ชั่นนี้สามารถนำไปใช้เพื่อเรียงลำดับองค์ประกอบข้อมูลในชุดองค์ประกอบระหว่างตำแหน่ง L และ H เฉพาะ

นั่นคือทั้งหมดสำหรับการเรียงลำดับที่รวดเร็ว