การเรียงลำดับอย่างรวดเร็วคือการค้นหาองค์ประกอบ (เดิมคุณสามารถค้นหาได้) เป็นข้อมูลอ้างอิง (pivot) จากนั้นพาร์ติชันอาร์เรย์เพื่อให้ค่าขององค์ประกอบทางด้านซ้ายของการอ้างอิงไม่สูงกว่าค่าอ้างอิงและค่า ขององค์ประกอบทางด้านขวาของการอ้างอิงไม่น้อยกว่าค่าอ้างอิง การเรียงลำดับอย่างรวดเร็วซ้ำ ๆ ปรับองค์ประกอบ N-1 อื่น ๆ ให้อยู่ในตำแหน่งที่ถูกต้องหลังจากการเรียงลำดับ ในที่สุดแต่ละองค์ประกอบอยู่ในตำแหน่งที่ถูกต้องหลังจากการเรียงลำดับและการเรียงลำดับเสร็จสิ้น ดังนั้นอัลกอริทึมหลักของอัลกอริทึมการเรียงลำดับอย่างรวดเร็วคือการดำเนินการแบ่งพาร์ติชันนั่นคือวิธีการปรับตำแหน่งของเกณฑ์มาตรฐานและปรับตำแหน่งสุดท้ายของเกณฑ์มาตรฐานคืนเพื่อแบ่งและพิชิตการเรียกซ้ำ
อัลกอริทึมสำหรับการเรียงลำดับอย่างรวดเร็วคือ:
1) ตั้งค่าตัวแปรสองตัว I และ J เมื่อการเรียงลำดับเริ่มต้น: i = 0, j = n-1;
2) ใช้องค์ประกอบอาร์เรย์แรกเป็นข้อมูลคีย์และกำหนดให้กับคีย์นั่นคือ key = a [0];
3) เริ่มต้นจาก j เพื่อค้นหาไปข้างหน้านั่นคือเริ่มจากด้านหลังเพื่อค้นหาไปข้างหน้า (j--) ค้นหาค่าแรก [j] เล็กกว่ากุญแจและเปลี่ยน A [j] และ a [i];
4) เริ่มจากฉันเพื่อค้นหาย้อนหลังนั่นคือเริ่มต้นจากด้านหน้าไปข้างหน้า (i ++) ค้นหา [i] แรกที่ใหญ่กว่ากุญแจและเปลี่ยน A [i] และ A [j];
5) ทำซ้ำขั้นตอนที่ 3 และ 4 จนกระทั่ง i = J; 4 ไม่เกินคีย์การเปลี่ยนแปลงค่าของ J และฉันดังนั้น j = j-1, i = i+1 จนกว่าจะพบ ยังคงไม่เปลี่ยนแปลง
ให้ฉันยกตัวอย่างสิ่งนี้อาจไม่เข้าใจง่าย สมมติว่าลำดับที่จะจัดเรียงคือ
การคัดลอกรหัสมีดังนี้:
แพ็คเกจ com.zc.manythread;
นำเข้า java.util.random;
-
* จัดเรียงอย่างรวดเร็ว
* @author Administrator
-
-
QSORT ชั้นเรียนสาธารณะ {
int [] วันที่;
QSORT สาธารณะ (int [] วันที่) {
this.date = วันที่;
-
-
* ฟังก์ชั่นแลกเปลี่ยน
* @param a
* @param i
* @param J
-
การแลกเปลี่ยนโมฆะส่วนตัว (int a [], int i, int j) {
int t;
t = a [i];
a [i] = a [j];
a [j] = t;
-
-
* การจัดเรียงฟังก์ชั่น
* @param a
* @param lo0
* @param hi0
* @กลับ
-
int [] quicksort (int a [], int lo0, int hi0) {// วิธีการแบ่งและการรักษาคือการแบ่งอาร์เรย์ออกเป็น [lo0..q-1] และ [q+1..hi0]
int lo = lo0;
int hi = hi0;
int กลาง;
ถ้า (hi0> lo0) {
mid = a [(hi0+lo0)/2];
ในขณะที่ (lo <= hi) {
ในขณะที่ ((lo <hi0) && (a [lo] <mid)) ++ lo;
ในขณะที่ ((hi> lo0) && (a [hi]> mid)) -hi;
ถ้า (lo <= hi) {
swap (a, lo, hi);
++ lo;
--สวัสดี;
-
-
ถ้า (lo0 <hi) {
Quicksort (a, lo0, hi);
-
ถ้า (lo <hi0) {
Quicksort (a, lo, hi0);
-
-
กลับ A;
-
-
-
* สร้างข้อมูลอาร์เรย์ที่ซ้ำกัน
-
INT แบบคงที่ส่วนตัว [] สร้างขึ้น (จำนวน int) {
int [] data = new int [count];
สำหรับ (int i = 0; i <data.length; i ++) {
ข้อมูล [i] = (int) (math.random ()*นับ);
-
ส่งคืนข้อมูล
-
-
* ไม่มีข้อมูลอาร์เรย์ที่ซ้ำกัน
* @param นับ
* @กลับ
-
INT แบบคงที่ส่วนตัว [] COMLETATE1 (จำนวน int) {
int [] data = new int [count];
สุ่มแรนด์ = ใหม่สุ่ม ();
บูลีน [] บูล = บูลีนใหม่ [100];
int num = 0;
สำหรับ (int i = 0; i <count; i ++) {
ทำ {
// หากหมายเลขที่สร้างขึ้นเหมือนกันให้วนลูปดำเนินการต่อ
num = rand.nextint (100);
} ในขณะที่ (bool [num]);
บูล [num] = true;
ข้อมูล [i] = num;
-
ส่งคืนข้อมูล
-
/************ ฟังก์ชั่นหลัก *********************/
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
จำนวน int สุดท้าย = 10;
int [] data = comentate1 (นับ);
สำหรับ (int n: data) {
System.out.print (n+"/t");
-
QSORT DATA1 = ใหม่ QSORT (ข้อมูล);
System.out.println ();
int [] a = data1.quicksort (ข้อมูล, 0, count-1);
สำหรับ (int n: a) {
System.out.print (n+"/t");
-
-
-
ผลลัพธ์มีดังนี้:
ข้างต้นเป็นเนื้อหาทั้งหมดที่อธิบายไว้ในบทความนี้