แทรกการเรียงลำดับโดยตรง
1 แนวคิดการเรียงลำดับ:
บันทึก RI ที่จะเรียงลำดับจะถูกแทรกลงในบันทึกที่เรียงลำดับแล้ว R1, R2, ... , R (N-1)
สำหรับลำดับการสุ่มเริ่มต้นจากองค์ประกอบที่สองแทรกองค์ประกอบลงในตำแหน่งที่สอดคล้องกันในองค์ประกอบก่อนที่จะกลับมา องค์ประกอบก่อนที่มันจะถูกจัดเรียง
ลำดับแรก: แทรกองค์ประกอบที่สองลงในรายการที่สั่งซื้อในลำดับก่อนหน้า (ในเวลานี้มีเพียงองค์ประกอบเดียวในองค์ประกอบก่อนหน้านี้แน่นอนว่ามีการสั่งซื้อ) หลังจากนั้นองค์ประกอบสององค์ประกอบแรกของลำดับนี้จะถูกสั่งซื้อ
การเรียงลำดับที่สอง: แทรกองค์ประกอบที่สามลงในรายการที่สั่งซื้อของความยาวก่อนหน้า 2 เพื่อให้องค์ประกอบสององค์ประกอบแรกได้รับการสั่งซื้อ
และอื่น ๆ จนกว่าจะมีการแทรกองค์ประกอบที่ n ลงในรายการที่สั่งซื้อของความยาวก่อนหน้า (N-1)
2 การใช้อัลกอริทึม:
// แทรกการเรียงลำดับโดยตรง void straight_insert_sort (int num [], int len) {int i, j, key; สำหรับ (j = 1; j <len; j ++) {key = num [j]; i = j-1; ในขณะที่ (i> = 0 && num [i]> คีย์) {num [i+1] = num [i]; ฉัน--; } num [i+1] = key; -3 การวิเคราะห์ประสิทธิภาพ:
3.1 ความซับซ้อนของอวกาศ: ดังที่ได้กล่าวไว้ข้างต้นใช้คีย์หน่วยเสริมและความซับซ้อนของอวกาศคือ O (1)
3.2 ความซับซ้อนของเวลา:
3.2.1 กรณีที่ดีที่สุด: บันทึกที่จะเรียงลำดับได้รับคำสั่งแล้วจากนั้นจัดเรียงในการเดินทางครั้งเดียวคำหลักจะถูกเปรียบเทียบหนึ่งครั้งและบันทึกจะถูกย้ายสองครั้ง กระบวนการทั้งหมด
จำนวนการเปรียบเทียบคือ
จำนวนบันทึกการเคลื่อนไหวคือ
ความซับซ้อนของเวลา o (n)
3.2.2 กรณีที่เลวร้ายที่สุด: บันทึกที่จะเรียงลำดับนั้นอยู่ในลำดับย้อนกลับแล้วเวลาเปรียบเทียบคำหลักคือ I (จาก I-1 ถึง 0) และบันทึกการเคลื่อนไหว (i+2) ครั้ง กระบวนการทั้งหมด
จำนวนการเปรียบเทียบคือ
จำนวนบันทึกการเคลื่อนไหวคือ
ความซับซ้อนของเวลา o (n^2)
3.2.3 ความซับซ้อนของเวลาเฉลี่ย: o (n^2)
3.3 ความเสถียร: เสถียร
พับครึ่งแทรกเรียงลำดับ
1 แนวคิดการเรียงลำดับ:
ขึ้นอยู่กับการเรียงลำดับโดยตรงบันทึกที่จะเรียงลำดับ RI จะถูกแทรกลงในบันทึกที่เรียงลำดับแล้ว R1, R2, ... , R (N-1) เนื่องจากบันทึก R1, R2, ... , R (N-1) ได้รับการจัดเรียงแล้วสามารถใช้ "การค้นหาครึ่ง" เมื่อมองหาตำแหน่งการแทรก
2 การใช้อัลกอริทึม:
// พับครึ่งแทรกการเรียงลำดับโมฆะ binary_insert_sort (int num [], int len) {int i, j, คีย์, ต่ำ, สูง, กลาง, กลาง; สำหรับ (i = 1; i <len; i ++) {key = num [i]; ต่ำ = 0; สูง = i-1; mid = (ต่ำ+สูง)/2; // ค้นหาจุดแทรกจุดแทรกสุดท้ายอยู่ในระดับต่ำในขณะที่ (ต่ำ <= สูง) {ถ้า (คีย์ <num [mid]) สูง = mid-1; อื่นต่ำ = กลาง+1; mid = (ต่ำ+สูง)/2; } // ย้ายบันทึกสำหรับ (j = i; j> low; j-) {num [j] = num [j-1]; } // แทรก Num Num [low] = key; -3 การวิเคราะห์ประสิทธิภาพ:
3.1 ความซับซ้อนของอวกาศ: ดังที่ได้กล่าวไว้ข้างต้นใช้คีย์หน่วยเสริมและความซับซ้อนของอวกาศคือ O (1)
3.2 ความซับซ้อนของเวลา: แม้ว่าการค้นหาแบบครึ่งสุดท้ายจะลดจำนวนระเบียนและการเปรียบเทียบ แต่ก็ไม่ได้ลดจำนวนการเคลื่อนไหวดังนั้นความซับซ้อนของเวลาจึงเหมือนกับอัลกอริทึมการค้นหาโดยตรง
3.2.1 กรณีที่ดีที่สุด: ความซับซ้อนของเวลา o (n)
3.2.2 กรณีที่เลวร้ายที่สุด: ความซับซ้อนของเวลา o (n^2)
3.2.3 ความซับซ้อนของเวลาเฉลี่ย: o (n^2)
3.3 ความเสถียร: เสถียร