บล็อกนี้ยึดตามแนวทางการแบ่งแยกและพิชิต Merge Sort คืออัลกอริทึม 'หารและพิชิต' ซึ่งปัญหาจะถูกแบ่งออกเป็นปัญหาย่อยจากนั้นจะรวมเข้าด้วยกันเพื่อพิชิตการแก้ปัญหา บล็อกนี้เกี่ยวกับ Merge Sort in จะแนะนำคุณผ่านหัวข้อด้านล่างโดยละเอียด -
- Merge Sort ใน Python คืออะไร?
- แนวทางการแบ่งแยกและพิชิต
- การใช้ Merge Sort ใน Python
- ผังงานสำหรับการใช้งาน Merge Sort
- ข้อดีและการใช้งาน
Merge Sort ใน Python คืออะไร?
Merge Sort ขึ้นอยู่กับอัลกอริทึมการแบ่งและพิชิตโดยที่อาร์เรย์อินพุตถูกแบ่งออกเป็นสองส่วนจากนั้นจัดเรียงแยกจากกันและผสานกลับเพื่อเข้าถึงโซลูชัน ฟังก์ชัน merge () ใช้สำหรับการผสานการเรียงลำดับ .
แนวทางการแบ่งแยกและพิชิต
- อาร์เรย์ถูกแบ่งครึ่งและทำซ้ำกระบวนการแต่ละครึ่งจนกว่าแต่ละครึ่งจะมีขนาด 1 หรือ 0
- อาร์เรย์ของขนาด 1 ถูกจัดเรียงเล็กน้อย
- ตอนนี้อาร์เรย์ที่เรียงลำดับทั้งสองรวมกันเป็นอาร์เรย์ขนาดใหญ่ และสิ่งนี้จะดำเนินต่อไปจนกว่าองค์ประกอบทั้งหมดจะรวมกันและเรียงลำดับอาร์เรย์
นี่คือการแสดงภาพของการเรียงลำดับการผสานเพื่อล้างภาพให้คุณ
การเรียนรู้เชิงลึกกับการเรียนรู้ของเครื่องเทียบกับการจดจำรูปแบบ
อินพุตอาร์เรย์ = [3,1,4,1,5,9,2,6,5,4]
ตอนนี้ให้เราดำเนินการต่อไป
การใช้ Merge Sort ใน Python
def mergeSort (nlist): print ('Splitting', nlist) ถ้า len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (righthalf) i = j = k = 0 ในขณะที่ iเอาท์พุต:
$ python main.py
(‘แยก‘, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(‘แยก‘, [3, 1, 4, 1, 5])
('แยก', [3, 1])
('แยก', [3])
('การรวม', [3])
('แยก', [1])
('การรวม', [1])
(‘การรวม‘, [1, 3])
(‘แยก‘, [4, 1, 5])
('แยก', [4])
('การรวม', [4])
(‘แยก‘, [1, 5])
('แยก', [1])
('การรวม', [1])
('แยก', [5])
('การรวม', [5])
(‘การรวม‘, [1, 5])
(‘การรวม‘, [1, 4, 5])
(‘การรวม‘, [1, 1, 3, 4, 5])
(‘แยก‘, [9, 2, 6, 5, 4])
(‘แยก‘, [9, 2])
(‘แยก‘, [9])
(‘การรวม‘, [9])
('แยก', [2])
('การรวม', [2])
(‘การรวม‘, [2, 9])
(‘แยก‘, [6, 5, 4])
(‘แยก‘, [6])
(‘การรวม‘, [6])
(‘แยก‘, [5, 4])
('แยก', [5])
('การรวม', [5])
('แยก', [4])
('การรวม', [4])
(‘การรวม‘, [4, 5])
(‘การรวม‘, [4, 5, 6])
(‘การรวม‘, [2, 4, 5, 6, 9])
(‘การรวม‘, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
java สแกนเนอร์คืออะไรผังงานสำหรับการใช้งาน Merge Sort
ข้อดีและการใช้งาน Merge Sort
อัลกอริทึมอื่น ๆ ส่วนใหญ่ทำงานไม่ดีกับโครงสร้างข้อมูลตามลำดับเช่นไฟล์และรายการที่เชื่อมโยง ในโครงสร้างเหล่านี้การเข้าถึงองค์ประกอบแบบสุ่มต้องใช้เวลาเชิงเส้นไม่ใช่เวลาคงที่ปกติ และลักษณะของการเรียงลำดับผสานทำให้ง่ายและรวดเร็วสำหรับโครงสร้างข้อมูลดังกล่าวหนึ่งในคุณสมบัติที่ดีที่สุดของการเรียงลำดับการผสานคือจำนวนการเปรียบเทียบที่ต่ำ ทำให้จำนวนการเปรียบเทียบ O (n * log (n)) แต่ปัจจัยคงที่นั้นดีเมื่อเทียบกับ Quicksort ซึ่งทำให้มีประโยชน์เมื่อฟังก์ชันเปรียบเทียบเป็นการทำงานที่ช้านอกจากนี้วิธีการแบ่งและพิชิตของการเรียงลำดับการผสานทำให้สะดวกสำหรับการประมวลผลแบบขนาน
ด้วยเหตุนี้เราจึงมาถึงจุดสิ้นสุดของบล็อกนี้เกี่ยวกับ“ วิธีใช้ Merge Sort ใน Python” ฉันหวังว่าเนื้อหาจะช่วยเพิ่มคุณค่าให้กับความรู้ของคุณใน Python หากต้องการรับความรู้เชิงลึกเกี่ยวกับ Python พร้อมกับแอพพลิเคชั่นต่างๆคุณสามารถลงทะเบียนเพื่อถ่ายทอดสด ด้วยการสนับสนุนตลอด 24 ชั่วโมงทุกวันและการเข้าถึงตลอดชีวิต