การเรียงลำดับโดยตรง
ความคิดในการแทรกการเรียงลำดับโดยตรงนั้นเข้าใจง่ายดูเหมือนว่า:
1. แบ่งอาร์เรย์ที่จะจัดเรียงเป็นสองส่วน: เรียงลำดับและไม่เรียงลำดับ ในตอนแรกองค์ประกอบแรกได้รับการพิจารณาว่าจะจัดเรียง
2. เริ่มต้นด้วยองค์ประกอบที่สองค้นหาตำแหน่งที่เหมาะสมขององค์ประกอบใน subarray ที่เรียงลำดับและแทรก
3. ทำซ้ำกระบวนการข้างต้นจนกว่าองค์ประกอบสุดท้ายจะถูกแทรกลงใน subarray ที่สั่งซื้อ
4. การเรียงลำดับเสร็จสมบูรณ์
ตัวอย่าง:
ความคิดนั้นง่าย แต่รหัสไม่ง่ายต่อการเขียนเหมือนการเรียงลำดับฟอง ก่อนอื่นวิธีการกำหนดตำแหน่งที่ถูกต้อง? มากกว่าหรือเท่ากับซ้ายน้อยกว่าหรือเท่ากับด้านขวา? ไม่ต้องพิจารณาเงื่อนไขขอบเขตมากมายและมีการตัดสินมากเกินไป ประการที่สองการแทรกองค์ประกอบลงในอาร์เรย์จะต้องมีการเคลื่อนย้ายองค์ประกอบจำนวนมากอย่างหลีกเลี่ยงไม่ได้ จะควบคุมการเคลื่อนไหวของพวกเขาได้อย่างไร?
ในความเป็นจริงนี่ไม่ใช่ปัญหากับอัลกอริทึมของตัวเองและมีบางอย่างเกี่ยวกับภาษาการเขียนโปรแกรม บางครั้งอัลกอริทึมเองก็เป็นผู้ใหญ่แล้วและยังคงต้องมีการเปลี่ยนแปลงเล็กน้อยเมื่อพูดถึงภาษาการเขียนโปรแกรมที่เฉพาะเจาะจง สิ่งที่เรากำลังพูดถึงที่นี่คืออัลกอริทึม Java ดังนั้นเรามาพูดถึง Java
เพื่อแก้ปัญหาข้างต้นเราได้ปรับแต่งขั้นตอนที่สองเล็กน้อย เราไม่ได้เริ่มการเปรียบเทียบจากตำแหน่งเริ่มต้นของการอาเรย์ย่อย แต่เริ่มการเปรียบเทียบผกผันจากหางของอาเรย์ย่อย ตราบใดที่มันมีขนาดใหญ่กว่าจำนวนที่ต้องแทรกเราก็เลื่อนไปข้างหลัง จนกว่าหมายเลขจะไม่มากกว่าตัวเลขจากนั้นจำนวนที่จะแทรกจะถูกวางไว้ในตำแหน่งที่ว่างเปล่านี้ ดังนั้นเราสามารถเขียนรหัสต่อไปนี้:
insertarray.java
Insertarray คลาสสาธารณะ {// Array Private Long [] arr; // ขนาดของข้อมูลที่ถูกต้องในอาร์เรย์ส่วนตัว int elems; // ค่าเริ่มต้นของตัวสร้างการแทรกสาธารณะ () {arr = ใหม่ยาว [50]; } public insertArray (int max) {arr = ใหม่ยาว [สูงสุด]; } // แทรกข้อมูลโมฆะสาธารณะ (ค่ายาว) {arr [elems] = ค่า; Elems ++; } // แสดงข้อมูลโมฆะสาธารณะข้อมูล () {สำหรับ (int i = 0; i <elems; i ++) {system.out.print (arr [i]+""); } system.out.println (); } // แทรกการเรียงลำดับโมฆะสาธารณะ insertSort () {long select = 0l; สำหรับ (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; สำหรับ (j = i; j> 0 && arr [j - 1]> = select; j--) {arr [j] = arr [j - 1]; } arr [j] = เลือก; - คลาสทดสอบ:
testinsertarray.java
Public Class TestInserTarray {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {insertarray iarr = new insertarray (); iarr.insert (85); iarr.insert (7856); iarr.insert (12); iarr.insert (8); iarr.insert (5); iarr.insert (56); iarr.display (); IARR.INSERTSORT (); iarr.display (); - ผลการพิมพ์:
ประสิทธิภาพ/ความซับซ้อนของอัลกอริทึม
ตอนนี้มาพูดคุยเกี่ยวกับความซับซ้อนของเวลาของอัลกอริทึมการแทรกโดยตรง โดยไม่คำนึงถึงอินพุตอัลกอริทึมจะทำการเรียงลำดับ N-1 รอบเสมอ อย่างไรก็ตามเนื่องจากจุดแทรกของแต่ละองค์ประกอบมีความไม่แน่นอนและได้รับผลกระทบอย่างมากจากข้อมูลอินพุตความซับซ้อนของมันจึงไม่แน่นอน เราสามารถหารือเกี่ยวกับสถานการณ์ที่ดีที่สุดเลวร้ายที่สุดและเฉลี่ย
1. กรณีที่ดีที่สุด: จากลักษณะของอัลกอริทึมจะเห็นได้ว่าเมื่ออาร์เรย์ที่จะจัดเรียงนั้นอยู่ในลำดับที่เป็นบวก (อาร์เรย์ได้รับคำสั่งและคำสั่งซื้อก็เหมือนกับคำสั่งที่ต้องการ เหตุผลก็คือในกรณีนี้แต่ละองค์ประกอบจะต้องเปรียบเทียบเพียงครั้งเดียวและไม่จำเป็นต้องย้าย ความซับซ้อนของเวลาของอัลกอริทึมคือ o (n);
2. กรณีที่เลวร้ายที่สุด: เห็นได้ชัดว่าเมื่ออาร์เรย์ที่จะจัดเรียงอยู่ในลำดับย้อนกลับมันเป็นกรณีที่เลวร้ายที่สุด ในกรณีนี้จำนวนการเปรียบเทียบต่อรอบคือ I-1 และจำนวนการมอบหมายคือฉัน จำนวนครั้งทั้งหมดคือผลรวมของเงื่อนไข N แรกของซีรี่ส์ 2N-1 นั่นคือ N^2 ความซับซ้อนของเวลาของอัลกอริทึมคือ o (n^2);
3. สถานการณ์เฉลี่ย: จากการวิเคราะห์ข้างต้นเราสามารถรับได้ว่าจำนวนการดำเนินงานของอัลกอริทึมภายใต้สถานการณ์เฉลี่ยอยู่ที่ประมาณ (n^2)/2 (หมายเหตุ: การคำนวณที่นี่ขึ้นอยู่กับการมอบหมายและการเปรียบเทียบหากเป็นไปตามการเคลื่อนไหวและการเปรียบเทียบ เห็นได้ชัดว่าความซับซ้อนของเวลายังคงเป็น o (n^2)
สำหรับความซับซ้อนเชิงพื้นที่ของอัลกอริทึมการเคลื่อนไหวทั้งหมดจะดำเนินการภายในข้อมูล ค่าใช้จ่ายเพียงอย่างเดียวคือเราแนะนำตัวแปรชั่วคราว (โครงสร้างข้อมูลบางอย่างเรียกว่า "Sentinels" ในหนังสือ) ดังนั้นความซับซ้อนเชิงพื้นที่ (พื้นที่พิเศษ) คือ O (1)
ความเสถียรของอัลกอริทึม
เนื่องจากคุณเพียงแค่ต้องหาตำแหน่งที่ไม่เกินจำนวนปัจจุบันและไม่จำเป็นต้องเปลี่ยนการแทรกการเรียงลำดับโดยตรงเป็นวิธีการเรียงลำดับที่เสถียร
ตัวแปรอัลกอริทึม
หากมีข้อมูลจำนวนมากที่จะจัดเรียงมันจะทำให้เกิดค่าใช้จ่ายจำนวนมากทุกครั้งที่คุณมองจากด้านหลังไปด้านหน้า เพื่อปรับปรุงความเร็วในการค้นหาการค้นหาแบบไบนารีสามารถใช้สำหรับการเพิ่มประสิทธิภาพประสิทธิภาพ เนื่องจากประสิทธิภาพของการค้นหาแบบไบนารีนั้นสูงมากความซับซ้อนของ O (n) จึงมั่นใจได้และประสิทธิภาพการค้นหาสามารถปรับปรุงได้อย่างมากเมื่อมีข้อมูลมากขึ้นหรือข้อมูลอินพุตมีแนวโน้มที่จะเลวร้ายที่สุด ในหนังสือบางเล่มวิธีนี้เรียกว่าการพับและการเรียงลำดับครึ่ง การใช้รหัสนั้นค่อนข้างซับซ้อนและสามารถโพสต์ได้หากคุณมีเวลาในอนาคต
นอกจากนี้ยังมีการเรียงลำดับการแทรกแบบ 2 ทางและประเภทแทรกตาราง การเรียงลำดับการแทรก 2 ทางได้รับการปรับปรุงเพิ่มเติมบนพื้นฐานของการเรียงลำดับการพับและการแทรกครึ่งและจำนวนการเคลื่อนไหวของมันลดลงอย่างมากประมาณ n^2/8 อย่างไรก็ตามมันไม่ได้หลีกเลี่ยงจำนวนการเคลื่อนไหวและไม่ลดระดับความซับซ้อน การเรียงลำดับการแทรกตารางจะเปลี่ยนโครงสร้างการจัดเก็บอย่างสมบูรณ์และไม่ย้ายระเบียน แต่รายการที่เชื่อมโยงจะต้องได้รับการบำรุงรักษาและตัวชี้ของรายการที่เชื่อมโยงนั้นได้รับการแก้ไขแทนการย้ายระเบียน ดังนั้นความซับซ้อนของมันยังคงเป็น o (n^2)
สำหรับการเรียงลำดับการแทรกแบบ 2 ทางและการเรียงลำดับการแทรกตารางคุณสามารถอ้างถึงหนังสือ "โครงสร้างข้อมูล" ที่แก้ไขโดย Yan Weimin และ Wu Weimin
อัลกอริทึมสถานการณ์ที่ใช้งานได้
การเรียงลำดับการแทรกไม่สามารถใช้ได้เมื่ออาร์เรย์มีขนาดใหญ่เนื่องจากความซับซ้อนของ O (n^2) อย่างไรก็ตามเมื่อมีข้อมูลค่อนข้างน้อยมันเป็นตัวเลือกที่ดีโดยทั่วไปใช้เป็นส่วนขยายสำหรับการเรียงลำดับอย่างรวดเร็ว ตัวอย่างเช่นในอัลกอริทึมการเรียงลำดับของ STL และอัลกอริทึม QSort ของ STDLIB การเรียงลำดับการแทรกจะใช้เป็นอาหารเสริมเพื่อการเรียงลำดับอย่างรวดเร็วและใช้ในการจัดเรียงองค์ประกอบจำนวนน้อย ตัวอย่างเช่นในการใช้วิธีการเรียงลำดับที่ใช้ใน JDK 7 java.util.Arrays เมื่อความยาวของอาร์เรย์ที่จะจัดเรียงน้อยกว่า 47 จะใช้การเรียงลำดับการแทรก