จะทำการ Merge Sort ใน Java ได้อย่างไร?

บทความนี้เกี่ยวกับ Merge Sort ใน Java จะช่วยให้คุณเข้าใจวิธีการจัดเรียงรายการขององค์ประกอบโดยใช้การจัดเรียงการผสานด้วยความช่วยเหลือของโปรแกรมตัวอย่าง

เคยได้ยินเกี่ยวกับคำว่า“ Divide and Conquer” หรือไม่? บทความนี้ค่อนข้างอิงตามแนวทางนี้โดยเฉพาะ ผสานการเรียง คืออัลกอริทึม 'หารและพิชิต' ที่เราแบ่งปัญหาออกเป็นปัญหาย่อยก่อนแล้วรวมเข้าด้วยกันเพื่อพิชิตวิธีแก้ปัญหาของเรา นี่คือภาพรวมที่สมบูรณ์ของแนวคิดการเรียงลำดับการผสานใน J .

เอาล่ะ!





merge sort ใน Java คืออะไร?

การเรียงลำดับการผสานเป็นหนึ่งในความนิยม อัลกอริทึมการเรียงลำดับ ใช้ได้และเป็นไปตามแนวทางการแบ่งแยกและพิชิต ปัญหาแบ่งออกเป็นปัญหาย่อยและรวมเข้าด้วยกันเพื่อไปสู่ทางออกสุดท้าย!

ตอนนี้เกิดอะไรขึ้นระหว่างการทำงานของการเรียงลำดับการผสาน? ให้เราเข้าใจโดยละเอียด



การทำงานของการเรียงลำดับการผสาน

มีสองขั้นตอนตามด้วยการเรียงลำดับการผสานระหว่างกระบวนการ:

  • การแบ่ง: ในขั้นตอนนี้อาร์เรย์อินพุตแบ่งออกเป็น 2 ส่วนโดยเดือยคือจุดกึ่งกลางของอาร์เรย์ ขั้นตอนนี้จะดำเนินการแบบวนซ้ำสำหรับอาร์เรย์ครึ่งหนึ่งทั้งหมดจนกว่าจะไม่มีอาร์เรย์ครึ่งหนึ่งให้หารเพิ่มเติม
  • พิชิต: ในขั้นตอนนี้เราจัดเรียงและรวมอาร์เรย์ที่แบ่งจากล่างขึ้นบนและเข้าถึงอาร์เรย์ที่เรียงลำดับของเรา

วิธีนี้ช่วยให้คุณจัดเรียงส่วนย่อยของปัญหาได้อย่างง่ายดายก่อนจึงไปถึงแนวทางแก้ไข

ผมขอแสดงภาพของการเรียงลำดับการผสาน



ตัวอย่าง: แผนภาพ

ผสานการเรียง - Edureka

ที่นี่คุณจะเห็นว่าการเรียงลำดับการผสานมีลักษณะอย่างไร แนวคิดหลักของการจัดเรียงแบบผสานคือใช้เวลาในการจัดเรียงน้อยลง ตอนนี้กำลังก้าวไปสู่ส่วนการใช้งานของเรา!

การนำไปใช้

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)

การตัดแต่งทำอะไรใน java

O (n บันทึก n)

O (n บันทึก n)

ความซับซ้อนของอวกาศ

-

-

บน)

ด้วยเหตุนี้ฉันจะสรุปบทความนี้ ฉันหวังว่าเนื้อหาที่อธิบายข้างต้นจะเพิ่มคุณค่าให้กับความรู้ Java ของคุณ เราจะสำรวจโลก Java ไปด้วยกัน คอยติดตาม!

ตรวจสอบไฟล์ โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ซึ่งมีเครือข่ายผู้เรียนที่พึงพอใจมากกว่า 250,000 คนกระจายอยู่ทั่วโลก หลักสูตรการฝึกอบรมและการรับรอง Java J2EE และ SOA ของ Edureka ออกแบบมาสำหรับนักเรียนและผู้เชี่ยวชาญที่ต้องการเป็น Java Developer หลักสูตรนี้ออกแบบมาเพื่อให้คุณเริ่มต้นการเขียนโปรแกรม Java และฝึกอบรมแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับเฟรมเวิร์ก Java ต่างๆเช่น Hibernate & Spring

มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของ ' ผสานการเรียงลำดับใน Java ” บล็อกและเราจะติดต่อกลับโดยเร็วที่สุด