เคยได้ยินเกี่ยวกับคำว่า“ Divide and Conquer” หรือไม่? บทความนี้ค่อนข้างอิงตามแนวทางนี้โดยเฉพาะ ผสานการเรียง คืออัลกอริทึม 'หารและพิชิต' ที่เราแบ่งปัญหาออกเป็นปัญหาย่อยก่อนแล้วรวมเข้าด้วยกันเพื่อพิชิตวิธีแก้ปัญหาของเรา นี่คือภาพรวมที่สมบูรณ์ของแนวคิดการเรียงลำดับการผสานใน J .
merge sort ใน Java คืออะไร?
การเรียงลำดับการผสานเป็นหนึ่งในความนิยม อัลกอริทึมการเรียงลำดับ ใช้ได้และเป็นไปตามแนวทางการแบ่งแยกและพิชิต ปัญหาแบ่งออกเป็นปัญหาย่อยและรวมเข้าด้วยกันเพื่อไปสู่ทางออกสุดท้าย!
ตอนนี้เกิดอะไรขึ้นระหว่างการทำงานของการเรียงลำดับการผสาน? ให้เราเข้าใจโดยละเอียด
การทำงานของการเรียงลำดับการผสาน
มีสองขั้นตอนตามด้วยการเรียงลำดับการผสานระหว่างกระบวนการ:
- การแบ่ง: ในขั้นตอนนี้อาร์เรย์อินพุตแบ่งออกเป็น 2 ส่วนโดยเดือยคือจุดกึ่งกลางของอาร์เรย์ ขั้นตอนนี้จะดำเนินการแบบวนซ้ำสำหรับอาร์เรย์ครึ่งหนึ่งทั้งหมดจนกว่าจะไม่มีอาร์เรย์ครึ่งหนึ่งให้หารเพิ่มเติม
- พิชิต: ในขั้นตอนนี้เราจัดเรียงและรวมอาร์เรย์ที่แบ่งจากล่างขึ้นบนและเข้าถึงอาร์เรย์ที่เรียงลำดับของเรา
วิธีนี้ช่วยให้คุณจัดเรียงส่วนย่อยของปัญหาได้อย่างง่ายดายก่อนจึงไปถึงแนวทางแก้ไข
ผมขอแสดงภาพของการเรียงลำดับการผสาน
ตัวอย่าง: แผนภาพ
ที่นี่คุณจะเห็นว่าการเรียงลำดับการผสานมีลักษณะอย่างไร แนวคิดหลักของการจัดเรียงแบบผสานคือใช้เวลาในการจัดเรียงน้อยลง ตอนนี้กำลังก้าวไปสู่ส่วนการใช้งานของเรา!
การนำไปใช้
package MyPackage คลาสสาธารณะ MergeSort {void merge (int arr [], int beg, int mid, int end) {int l = mid - beg + 1 int r = end - mid int LeftArray [] = new int [l] int RightArray [] = int ใหม่ [r] สำหรับ (int i = 0 iเอาท์พุต:
เรียงลำดับอาร์เรย์
หนึ่ง
4
17
22
2. 3
40
สี่ห้า
51
55
90นี่คือลักษณะของโค้ด Java ที่แสดงถึงการเรียงลำดับการผสาน ก้าวไปสู่ส่วนต่อไป
ความซับซ้อน
ความซับซ้อนแบ่งออกเป็นสองประเภท: ความซับซ้อนของเวลาและความซับซ้อนของอวกาศ ในกรณีของการจัดเรียงแบบผสานข้อมูลจะเป็นดังที่แสดงด้านล่าง:
ความซับซ้อน กรณีที่ดีที่สุด
กรณีเฉลี่ย
กรณีที่เลวร้ายที่สุด
ความซับซ้อนของเวลา
O (n บันทึก n)
การตัดแต่งทำอะไรใน javaO (n บันทึก n)
O (n บันทึก n)
ความซับซ้อนของอวกาศ
-
-
บน)
ด้วยเหตุนี้ฉันจะสรุปบทความนี้ ฉันหวังว่าเนื้อหาที่อธิบายข้างต้นจะเพิ่มคุณค่าให้กับความรู้ Java ของคุณ เราจะสำรวจโลก Java ไปด้วยกัน คอยติดตาม!
ตรวจสอบไฟล์ โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ซึ่งมีเครือข่ายผู้เรียนที่พึงพอใจมากกว่า 250,000 คนกระจายอยู่ทั่วโลก หลักสูตรการฝึกอบรมและการรับรอง Java J2EE และ SOA ของ Edureka ออกแบบมาสำหรับนักเรียนและผู้เชี่ยวชาญที่ต้องการเป็น Java Developer หลักสูตรนี้ออกแบบมาเพื่อให้คุณเริ่มต้นการเขียนโปรแกรม Java และฝึกอบรมแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับเฟรมเวิร์ก Java ต่างๆเช่น Hibernate & Spring
มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของ ' ผสานการเรียงลำดับใน Java ” บล็อกและเราจะติดต่อกลับโดยเร็วที่สุด