ภาพรวมอัลกอริทึม/แนวคิด
การเรียงลำดับการผสานขึ้นอยู่กับกลยุทธ์ที่เรียกว่า "Divide and Conquer" แนวคิดพื้นฐานมีดังนี้:
1. สำหรับสองอาร์เรย์ที่สั่งซื้อเพื่อรวมเข้ากับอาร์เรย์ที่สั่งซื้อเราสามารถเขียนรหัสต่อไปนี้ได้อย่างง่ายดาย:
// ทั้ง A และ B คือ Ascend.public Void Merge (int [] a, int [] b, int [] c) {int i = 0, j = 0, k = 0; ในขณะที่ (i <= a.length && j <= b.length) {ถ้า (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} ในขณะที่ (i <= a.length) {c [k ++] = a [i ++]; - เป็นเรื่องง่ายที่จะเห็นว่าอัลกอริทึมการรวมนั้นมีประสิทธิภาพและความซับซ้อนของเวลาสามารถเข้าถึง O (n) ได้
2. หากมีอาร์เรย์ที่ไม่ได้เรียงลำดับซึ่งจำเป็นต้องจัดเรียง แต่สอง subarrays ที่แบ่งออกอย่างสมบูรณ์ A และ B ได้รับคำสั่งแยกต่างหากเรายังสามารถนำไปใช้กับพวกเขาได้อย่างง่ายดายด้วยความช่วยเหลือของรหัสข้างต้น
3. ดังนั้นฉันควรทำอย่างไรถ้า A และ B ไม่เป็นระเบียบ? คุณสามารถแบ่งออกเป็นอาร์เรย์ที่เล็กกว่า
4. ถ้าคุณแบ่งมันไปจนถึงที่เล็กที่สุดแต่ละ subarray มีเพียงองค์ประกอบเดียวก็ถือได้ว่าเป็นอาร์เรย์ที่สั่งซื้อ
5. เริ่มต้นด้วยอาร์เรย์ที่เล็กที่สุดเหล่านี้รวมเข้ากับขั้นตอนข้างต้นและจัดเรียงอาร์เรย์ทั้งหมด
ในระยะสั้นการเรียงลำดับการรวมคือการใช้การเรียกซ้ำการสลายตัวของอาร์เรย์เป็น subarray ก่อนแล้วจึงรวมอาร์เรย์เข้าด้วยกัน
ตัวอย่าง
นี่คือตัวอย่าง หากคุณต้องการเรียงลำดับอาร์เรย์ a = {2,1,3,5,2,3} จากนั้นแบ่งอาร์เรย์ออกเป็นสอง subarrays: {2,1,3} และ {5,2,3} หลังจากเรียงลำดับ subarrays ทั้งสองนี้พวกเขาจะกลายเป็น {1,2,3} และ {2,3,5} จากนั้นรวมทั้งสองอาร์เรย์เพื่อรับอาร์เรย์ที่สั่งซื้อขั้นสุดท้าย การใช้งานรหัสมีดังนี้:
Void sort (int [] a) {int [] aux = new int [A.Length]; // aux array mergesort (a, 0, a.length - 1, aux);} void mergesort (int [] a, int lo, int hi, int [] aux) {ถ้า (hi <= lo) กลับ; int mid = lo + (hi - lo) / 2; Mergesort (a, lo, mid, aux); Mergesort (a, mid + 1, hi, aux); ผสาน (a, lo, mid, hi, aux);} void merge (int [] a, int lo, int mid, int hi, int [] aux) {int i = lo, j = mid + 1; สำหรับ (int k = lo; k <= hi; k ++) {aux [k] = a [k]; } สำหรับ (int k = lo; k <= hi; k ++) {ถ้า (i> mid) a [k] = aux [j ++]; อย่างอื่นถ้า (j> hi) a [k] = aux [i ++]; อื่นถ้า (aux [i] <= aux [j]) a [k] = aux [i ++]; อื่น A [k] = aux [j ++]; - การใช้งานอื่น: การเรียงลำดับจากล่างขึ้นบน
ในการดำเนินการข้างต้นมันเทียบเท่ากับการแบ่งปัญหาใหญ่ออกเป็นปัญหาเล็ก ๆ และการแก้ปัญหาแยกต่างหากจากนั้นใช้คำตอบสำหรับปัญหาเล็ก ๆ ทั้งหมดเพื่อแก้ปัญหาใหญ่ทั้งหมด การแบ่งการเรียงลำดับของอาร์เรย์ขนาดใหญ่เป็นอาร์เรย์ขนาดเล็กการเรียงลำดับของการเรียงลำดับเป็นการเรียงลำดับจากบนลงล่าง มีการใช้งานอื่นที่มีการเรียงลำดับจากล่างขึ้นบนนั่นคือการรวมสองครั้งแรกจากนั้นรวมสี่และสี่ ... การใช้งานรหัสมีดังนี้:
เป็นโมฆะเรียงลำดับ (int [] a) {int n = a.length; int [] aux = new int [n]; สำหรับ (int sz = 1; sz <n; sz + = sz) {สำหรับ (int lo = 0; lo <n - sz; lo + = sz + sz) {// ในแต่ละรอบของการผสานการอาร์เรย์ย่อยที่สองที่รวมกันเป็นครั้งสุดท้าย -