การเรียงลำดับผสานหมายถึงการเรียงลำดับโดยการหารและพิชิต:
(1) แบ่งอาร์เรย์ออกเป็นสองอาร์เรย์เล็ก ๆ และจัดเรียงแยกต่างหาก
(2) จากนั้นรวมอาร์เรย์ที่แยกจากกันของคำสั่งซื้อที่เรียงลำดับ;
การคัดลอกรหัสมีดังนี้:
นำเข้า java.util.scanner;
คลาสสาธารณะ Mergesort {
int [] a = null;
int [] b = null;
int n;
สแกนเนอร์บาป = null;
Mergesort ()
-
a = new int [10,000];
b = ใหม่ int [10,000];
SIN = สแกนเนอร์ใหม่ (System.in);
-
Void Sort (int start, int end) // เรียงลำดับ [start ... end]
-
int กลาง;
if (start> = end) // เมื่อมีเพียงองค์ประกอบเดียวให้ส่งคืนโดยตรง
กลับ ;
อื่น
-
mid = (end-start)/2;
เรียงลำดับ (เริ่มต้นเริ่ม+กลาง);
เรียงลำดับ (เริ่ม+mid+1, สิ้นสุด);
// รวมสองอาร์เรย์ที่สั่งซื้อ [เริ่ม ... เริ่ม+กลาง] และ [เริ่ม+กลาง+1 ... สิ้นสุด]
ผสาน (เริ่มต้นเริ่ม+กลางปลาย);
-
-
Void Merge (int start, int mid, int end) // การรวมกัน
-
int t = เริ่ม;
int i = start, j = mid+1;
ในขณะที่ (i <= mid && j <= สิ้นสุด)
-
ถ้า (a [i] <a [j])
b [t ++] = a [i ++];
อื่น
b [t ++] = a [j ++];
-
ในขณะที่ (i <= mid)
b [t ++] = a [i ++];
ในขณะที่ (j <= สิ้นสุด)
b [t ++] = a [j ++];
สำหรับ (i = start; i <= end; i ++) // เขียนเนื้อหาที่จัดเรียงกลับไปยังตำแหน่งที่สอดคล้องกันของอาร์เรย์ก
a [i] = b [i];
-
เป็นโมฆะ Run ()
-
System.out.print ("ป้อนจำนวนตัวเลขที่จะเรียงลำดับ:");
n = sin.nextint ();
สำหรับ (int i = 0; i <n; i ++)
a [i] = sin.nextint ();
เรียงลำดับ (0, n-1);
System.out.println ("ผลการเรียงลำดับคือ:");
// ป้อนข้อมูลที่จะจัดเรียง
สำหรับ (int i = 0; i <n; i ++)
System.out.println (a [i]+"");
-
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
ใหม่ Mergesort (). run ();
-
-