ประเภทของการปรับปรุงใน การเรียง ลำดับเดือดคือถ้าลำดับการบันทึกเริ่มต้นได้รับการสั่งซื้อหรือสั่งโดยคำหลักโดยทั่วไปมันจะเสื่อมสภาพลงในการเรียงลำดับเดือด มีการใช้หลักการของการเรียกซ้ำและประสิทธิภาพเฉลี่ยที่ดีที่สุดในวิธีการเรียงลำดับทั้งหมดของลำดับขนาดเดียวกัน (n longn) ในแง่ของเวลาเฉลี่ยปัจจุบันถือว่าเป็นวิธีการเรียงลำดับภายในที่ดีที่สุด
แนวคิดพื้นฐานคือ: แบ่งข้อมูลที่จะจัดเรียงออกเป็นสองส่วนอิสระโดยการเรียงลำดับและข้อมูลทั้งหมดในส่วนนั้นมีขนาดเล็กกว่าข้อมูลทั้งหมดในส่วนอื่น ๆ จากนั้นจัดเรียงข้อมูลทั้งสองนี้อย่างรวดเร็วตามวิธีนี้ . กระบวนการเรียงลำดับทั้งหมดสามารถดำเนินการซ้ำเพื่อให้ได้ข้อมูลทั้งหมดกลายเป็นลำดับที่สั่งซื้อ
สามพอยน์เตอร์: ตัวชี้แรกเรียกว่าตัวชี้ Pivotkey (Pivot) ตัวชี้ที่สองและตัวชี้ที่สามคือตัวชี้ซ้ายและตัวชี้ขวาตามลำดับชี้ไปที่ค่าซ้ายสุดและค่าที่ถูกต้องที่สุด ตัวชี้ด้านซ้ายและวิธีตัวชี้ด้านขวาจากทั้งสองด้านไปยังกลางในเวลาเดียวกัน เดือยจนถึงระดับที่สูงขึ้น
ต้องใช้สองฟังก์ชั่น:
①ฟังก์ชั่นการเรียกซ้ำโมฆะ public Static void Quicksort (int [] n, int ซ้าย, int ขวา)
②ฟังก์ชั่นเซ็กเมนต์ (ฟังก์ชั่นการเรียงลำดับอย่างรวดเร็ว) พาร์ติชัน int คงที่สาธารณะ (int [] n, int ซ้าย, int ขวา)
ซอร์สโค้ด Java (รันสำเร็จ):
การคัดลอกรหัสมีดังนี้:
Package Testsortalgorithm;
ชั้นเรียนสาธารณะ Quicksort {
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
int [] array = {49,38,65,97,76,13,27};
Quicksort (Array, 0, Array.Length - 1);
สำหรับ (int i = 0; i <array.length; i ++) {
System.out.println (Array [i]);
-
-
/*ก่อนเขียนอัลกอริทึมเป็นต้นแบบข้อมูลตามอาร์เรย์แล้วเขียนอัลกอริทึมความสามารถในการปรับขนาด อาร์เรย์ {49,38,65,97,76,13,27}}
-
public static void Quicksort (int [] n, int ซ้าย, int ขวา) {
int pivot;
ถ้า (ซ้าย <ขวา) {
// pivot เป็นเดือยองค์ประกอบที่เล็กกว่าอยู่ทางซ้ายและองค์ประกอบที่ใหญ่กว่าอยู่ทางขวา
pivot = พาร์ติชัน (n, ซ้าย, ขวา);
// โทรซ้ำได้อย่างรวดเร็วในอาร์เรย์ซ้ายและขวาจนกว่าคำสั่งซื้อจะถูกต้องอย่างสมบูรณ์
Quicksort (n, ซ้าย, pivot - 1);
Quicksort (n, pivot + 1, ขวา);
-
-
พาร์ติชัน int คงที่สาธารณะ (int [] n, int ซ้าย, int ขวา) {
int pivotkey = n [ซ้าย];
// เดือยจะไม่เปลี่ยนแปลงหลังจากได้รับการคัดเลือกและในที่สุดมันก็จะอยู่ตรงกลางโดยมีด้านหน้าเล็กและหลังใหญ่
ในขณะที่ (ซ้าย <ขวา) {
ในขณะที่ (ซ้าย <ขวา && n [ขวา]> = pivotkey) -ขวา;
// ย้ายองค์ประกอบที่เล็กกว่าเดือยไปยังจุดต่ำสุด
n [ซ้าย] = n [ขวา];
ในขณะที่ (ซ้าย <ขวา && n [ซ้าย] <= pivotkey) ++ ซ้าย;
// ย้ายองค์ประกอบที่ใหญ่กว่าเดือยไปยังจุดสูงสุด
n [ขวา] = n [ซ้าย];
-
// เมื่อซ้าย == ขวาให้ทำการเดินทางอย่างรวดเร็ว
n [ซ้าย] = Pivotkey;
กลับไปทางซ้าย;
-
-