ภาพรวม
วิธีการเรียงลำดับการรวมคือการรวมตารางที่สั่งซื้อสอง (หรือมากกว่าสอง) ไว้ในตารางที่สั่งซื้อใหม่นั่นคือแบ่งลำดับที่จะจัดเรียงเป็นหลายภาคต่อแต่ละลำดับจะถูกสั่งซื้อ จากนั้นการเรียงลำดับที่สั่งซื้อจะถูกรวมเข้ากับลำดับที่สั่งโดยรวม
การเรียงลำดับการผสานถูกนำมาใช้โดยใช้การเรียกซ้ำซึ่งเป็นของ "การหารและพิชิต" อาร์เรย์เป้าหมายจะถูกแบ่งออกเป็นสองส่วนจากกลางจากนั้นทั้งสองอาร์เรย์จะถูกจัดเรียงแยกกัน หลังจากการเรียงลำดับเสร็จสิ้นทั้งสองอาร์เรย์จะ "รวม" เข้าด้วยกัน สิ่งที่สำคัญที่สุดในการเรียงลำดับคือกระบวนการ "ผสาน" ในกระบวนการผสานพื้นที่เพิ่มเติมที่สอดคล้องกับสองอาร์เรย์ที่จำเป็นต้องรวมกันเป็นสิ่งจำเป็น
ภาพการทำซ้ำ:
ขั้นตอน
ใช้พื้นที่เพื่อให้ขนาดของมันคือผลรวมของสองลำดับที่เรียงลำดับ พื้นที่นี้ใช้ในการจัดเก็บลำดับที่ผสานเพื่อตั้งค่าตัวชี้สองตัว ตำแหน่งเริ่มต้นคือตำแหน่งเริ่มต้นของลำดับที่เรียงลำดับทั้งสองเปรียบเทียบองค์ประกอบที่ชี้ไปที่ตัวชี้สองตัวเลือกองค์ประกอบที่ค่อนข้างเล็กและนำมันเข้าไปในพื้นที่ที่ผสานและย้ายตัวชี้ไปยังตำแหน่งถัดไป ทำซ้ำขั้นตอนที่ 3 จนกว่าตัวชี้ถึงจุดสิ้นสุดของลำดับ คัดลอกองค์ประกอบที่เหลือทั้งหมดของลำดับอื่นโดยตรงไปยังจุดสิ้นสุดของลำดับที่ผสาน
ข้อมูลดิบ:
3 5 2 6 2
สิ่งที่จำเป็นสำหรับการรวมกันคือการแยกอาร์เรย์แบ่งออกเป็นสองแล้วแบ่งออกเป็นสองและพวกเขาไม่สามารถแบ่งได้อีกครั้งและรวมพวกเขา
รอบแรกถูกคั่น, ดัชนี 2 ((0+4)/2 = 2) คือกลาง
[3 5 2] [6 2]
รอบที่สองของการแยกแยก [3 5 2]
[3 5] [2] [6 2]
รอบที่สามของการแยกแยก [3 5]
[3] [5] [2] [6 2]
ผสาน [3] [5]
[3 5] [2] [6 2]
ผสาน [3 5] [2]
[2 3 5] [6 2]
รอบที่สี่ถูกแยกออกจากกัน [6 2]
[2 3 5] [6] [2]
ผสาน [6] [2]
[2 3 5] [2 6]
ผสาน [2 3 5] [2 6]
[2 2 3 5 6]
การใช้งานรหัส (Java)
แพ็คเกจ com.coder4j.main.arithmetic.sorting; คลาสสาธารณะผสาน {mark int คงที่ส่วนตัว = 0; / ** * ผสานการเรียงลำดับ * * @param array * @param low * @param สูง * @return * / ส่วนตัวคงที่ int [] sort (int [] อาร์เรย์, int ต่ำ, int สูง) {int mid = (ต่ำ + สูง) / 2; ถ้า (ต่ำ <สูง) {mark ++; System.out.println ("Throwth in Progress" + Mark + "การแยกที่ตามมา, รับ"); System.out.println ("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + สูง + "]"); // การเรียงลำดับอาร์เรย์ด้านซ้าย (อาร์เรย์, ต่ำ, กลาง); // การเรียงลำดับอาร์เรย์ขวา (อาร์เรย์, กลาง + 1, สูง); // การผสานซ้ายและขวา (อาร์เรย์, ต่ำ, กลาง, สูง); } return array; } / ** * รวมอาร์เรย์ * * @param array * @param low * @param mid * @param สูง * / โมฆะแบบคงที่ส่วนตัวผสาน (int [] อาร์เรย์, int ต่ำ, int กลาง, int สูง) {system.out.println ("ผสาน: [" + ต่ำ + "-" + " int [] temp = new int [สูง - ต่ำ + 1]; int i = ต่ำ; // ตัวชี้ซ้าย int j = mid + 1; // ตัวชี้ขวา int k = 0; // ย้ายหมายเลขที่เล็กกว่าไปยังอาร์เรย์ใหม่ก่อนในขณะที่ (i <= mid && j <= สูง) {ถ้า (อาร์เรย์ [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // อาจมีองค์ประกอบที่เหลืออยู่ในหนึ่งในสองอาร์เรย์ // ย้ายหมายเลขที่เหลืออยู่ทางซ้ายไปยังอาร์เรย์ในขณะที่ (i <= mid) {temp [k ++] = array [i ++]; } // เลื่อนหมายเลขที่เหลืออยู่ทางด้านขวาไปยังอาร์เรย์ในขณะที่ (j <= สูง) {temp [k ++] = array [j ++]; } // เขียนทับตัวเลขในอาร์เรย์อาร์เรย์ใหม่สำหรับ (int m = 0; m <temp.length; m ++) {array [m+ต่ำ] = temp [m]; }} / ** * ผสานการเรียงลำดับ * * @param array * @return * / public Static int [] sort (int [] array) {return sort (array, 0, array.length - 1); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (อาร์เรย์); System.out.println ("ผลลัพธ์สุดท้าย"); สำหรับ (int i: เรียงลำดับ) {system.out.print (i + ""); -ผลการทดสอบผลลัพธ์:
การแยกครั้งแรกกำลังดำเนินการและ [0-2] [3-4] กำลังดำเนินการและการแยกครั้งที่สองกำลังดำเนินการและ [0-1] [2-2] กำลังดำเนินการและการแยกที่สามกำลังดำเนินการและ [0-0] [1-1] ผสาน: [0-0] [3-3] [4-4] ผสาน: [3-3] และ [4-4] ผสาน: [0-2] และ [3-4] ผลลัพธ์สุดท้าย 2 2 2 5 6 6
หลังจากการทดสอบมันสอดคล้องกับผลลัพธ์ในตัวอย่าง