Insertion Sort ใน java เป็นอัลกอริธึมการเรียงลำดับที่เรียบง่ายและมีประสิทธิภาพซึ่งสร้างอาร์เรย์ที่เรียงลำดับสุดท้ายทีละองค์ประกอบโดยปกติจะดำเนินการเมื่อผู้ใช้มีชุดข้อมูลขนาดเล็ก ฉันจะพูดถึงหัวข้อต่อไปนี้:
- Insertion Sort คืออะไร?
- อัลกอริทึมของการเรียงลำดับการแทรก
- รหัสสำหรับการเรียงลำดับการแทรกใน Java
- ความซับซ้อนและขอบเขตกรณี
Insertion Sort คืออะไร?
Insertion Sort ใน java เป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพซึ่งจะสร้างอาร์เรย์ที่เรียงลำดับสุดท้ายทีละองค์ประกอบ องค์ประกอบจากข้อมูลอินพุตจะถูกลบออกหลังจากการทำซ้ำทุกครั้ง เปรียบเทียบกับค่าที่ใหญ่ที่สุดที่มีอยู่ในอาร์เรย์แล้วย้ายไปยังตำแหน่งที่ถูกต้อง เพื่อให้เข้าใจถึงการทำงานของการเรียงลำดับนี้ลองดูตัวอย่างนี้
อัลกอริทึมของการเรียงลำดับการแทรก
สมมติว่าเรามีอาร์เรย์ที่ไม่ได้เรียงลำดับ [6, 5, 15, 3, 9]
การวนซ้ำดัชนีครั้งที่ 1: ค่าที่ดัชนีที่ 1 คือ 5 ซึ่งน้อยกว่า 6 อาร์เรย์จะกลายเป็น [6, 6, 15, 2, 8] .
เมื่อถึงจุดเริ่มต้นของชุดองค์ประกอบเราวางค่าไว้ที่ดัชนี 0ตอนนี้อาร์เรย์กลายเป็น: [5, 6, 15, 3, 9]
การทำซ้ำดัชนีครั้งที่ 2 : ค่าที่ดัชนีที่ 2 คือ 15 ซึ่งมากกว่า 6 ไม่มีการเปลี่ยนแปลงใด ๆ ในอาร์เรย์
การทำซ้ำดัชนีครั้งที่ 3 : ค่าที่ดัชนีที่ 3 คือ 3 ค่าน้อยกว่า 15 ดังนั้นอาร์เรย์จึงกลายเป็น [5, 6, 15, 15, 9]
อธิบายความแตกต่างระหว่างวัตถุที่เปลี่ยนแปลงไม่ได้และไม่เปลี่ยนรูป
ค่า 3 ยังน้อยกว่า 6 ดังนั้นอาร์เรย์จึงเปลี่ยนเป็น [5, 6, 6, 15, 9]
3 มีขนาดเล็กกว่า 5 เช่นกัน อาร์เรย์ได้รับการแก้ไขอีกครั้งเป็น [5, 5, 6, 15, 9]
เมื่อถึงจุดเริ่มต้นของอาร์เรย์ 3 จะถูกวางไว้ที่ดัชนี 0 ตอนนี้อาร์เรย์ถูกกำหนดให้เป็น [3, 5, 6, 15, 9]
การทำซ้ำดัชนีครั้งที่ 4: ค่าที่ดัชนีที่ 4 คือ 9 ตามอัลกอริทึมที่คล้ายกันอาร์เรย์ที่เรียงลำดับสุดท้ายคือ: [3, 5, 6, 9, 15]
รหัสสำหรับการเรียงลำดับการแทรกใน Java
// โปรแกรม Java เพื่อใช้ Insertion Sort คลาสสาธารณะ InsertionEx {/ * ฟังก์ชันเพื่อจัดเรียงอาร์เรย์โดยใช้การเรียงลำดับการแทรก * / void sort (int a []) {int n = a.length for (int i = 1 i= 0 && a [j]> key) {a [j + 1] = a [j] j = j - 1} a [j + 1] = key}} / * ฟังก์ชันสำหรับพิมพ์อาร์เรย์ขนาด n * / โมฆะคง displayArray (int a []) {int n = a.length สำหรับ (int i = 0 i ความซับซ้อนและขอบเขตกรณี
ความซับซ้อนของเวลา : ความซับซ้อนของเวลาในการเรียงลำดับการแทรกคือ O (n * 2)
กรณีเขตแดน : เวลาสูงสุดที่ใช้ในการเรียงลำดับการแทรกคือเมื่อองค์ประกอบถูกเรียงลำดับย้อนกลับ หากจัดเรียงองค์ประกอบเรียบร้อยแล้วต้องใช้เวลาน้อยที่สุด
ผู้ใช้ใช้การเรียงลำดับการแทรกเมื่อจำนวนองค์ประกอบที่จะจัดเรียงมีจำนวนน้อยกว่า นอกจากนี้ยังสามารถใช้เมื่ออาร์เรย์ที่ระบุเกือบจะเรียงลำดับเช่นตัวเลขเพียงไม่กี่ตัวเท่านั้นที่ถูกใส่ผิดและไม่อยู่ในตำแหน่งที่เหมาะสม
วิธีออกจากโปรแกรม java
ด้วยเหตุนี้เราจึงมาถึงตอนท้ายของบทความ Insertion Sort ใน Java ค กำจัดไฟล์ โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ซึ่งมีเครือข่ายผู้เรียนที่พึงพอใจมากกว่า 250,000 คนกระจายอยู่ทั่วโลก หลักสูตรการฝึกอบรมและการรับรอง Java J2EE และ SOA ของ Edureka ออกแบบมาสำหรับนักเรียนและผู้เชี่ยวชาญที่ต้องการเป็น Java Developer หลักสูตรนี้ออกแบบมาเพื่อให้คุณเริ่มต้นการเขียนโปรแกรม Java และฝึกอบรมแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับเฟรมเวิร์ก Java ต่างๆเช่น Hibernate & Spring
มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบล็อก 'การจัดเรียงการแทรกใน Java' และเราจะติดต่อกลับโดยเร็วที่สุด