A) หลักการ : แต่ละครั้งเลือกองค์ประกอบที่เล็กที่สุดจากบันทึกที่จะจัดเรียงและวางไว้ในลำดับที่ท้ายลำดับการเรียงลำดับจนกว่าบันทึกทั้งหมดจะถูกจัดเรียง นั่นคือการเดินทางแต่ละครั้งจะถูกเลือกเป็นบันทึก I-TH ในลำดับที่สั่งซื้อระหว่าง N-I+1 (i = 1, 2, ... N-1) อัลกอริทึมที่ใช้ความคิดนี้ส่วนใหญ่รวมถึงการเรียงลำดับการเลือกอย่างง่ายการเรียงลำดับการเลือกต้นไม้และการเรียงลำดับฮีป (นี่คือการคัดเลือกตัวเลือกง่าย ๆ ทั่วไปเท่านั้น)
b) แนวคิดพื้นฐานของการเลือกการเรียงลำดับอย่างง่าย : ให้อาร์เรย์: int [] arr = {n ข้อมูลในนั้น}; การเรียงลำดับครั้งแรกเลือกข้อมูลที่เล็กที่สุดในข้อมูลที่จะเรียงลำดับ arr [1] ~ arr [n] และแลกเปลี่ยนกับ arr [1]; ครั้งที่สองเลือกข้อมูลที่เล็กที่สุดในข้อมูลที่จะเรียงลำดับ arr [2] ~ arr [n] และแลกเปลี่ยนกับ r [2]; และอื่น ๆ เลือกข้อมูลที่เล็กที่สุดในข้อมูลที่จะเรียงลำดับ arr [i] ~ arr [n] และแลกเปลี่ยนกับ r [i] จนกว่าการเรียงลำดับทั้งหมดจะเสร็จสิ้น
c) ตัวอย่าง : Array int [] arr = {5,2,8,4,9,1};
-
ลำดับแรก: ข้อมูลต้นฉบับ: 528491
ข้อมูลขั้นต่ำ 1, วาง 1 ก่อนนั่นคือ 1 และ 5 ตำแหน่งการแลกเปลี่ยน
เรียงลำดับผล: 128495
-
ลำดับที่สอง:
เปรียบเทียบข้อมูลที่อยู่นอก 1 {28495}, 2 นั้นเล็กที่สุด
เรียงลำดับผล: 128495
-
ลำดับที่สาม:
ข้อมูลอื่นที่ไม่ใช่ 1 และ 2 ถูกเปรียบเทียบ {8495}, 4 มีน้อยที่สุด 8 และ 4 มีการแลกเปลี่ยน
เรียงลำดับผลลัพธ์: 124895
-
ลำดับที่สี่:
ข้อมูลอื่น ๆ นอกเหนือจาก 1, 2, 4 ถูกเปรียบเทียบ {895}, 5 เป็นขั้นต่ำ, 8 และ 5 มีการแลกเปลี่ยน
เรียงลำดับผล: 124598
-
ลำดับที่ห้า:
ข้อมูลอื่น ๆ ที่ไม่ใช่ 1, 2, 4, 5 ถูกเปรียบเทียบ 8 มีน้อยที่สุด 8 และ 9 มีการแลกเปลี่ยน
เรียงลำดับผลลัพธ์: 124589
-
หมายเหตุ: วิธีการที่จะได้รับหมายเลขที่เล็กที่สุดในแต่ละคำสั่ง: สำหรับการวนรอบที่จะเปรียบเทียบกำหนดอุณหภูมิตัวแปรที่สาม ก่อนอื่นให้เปรียบเทียบตัวเลขสองตัวแรกใส่หมายเลขที่เล็กลงในอุณหภูมิแล้วใช้อุณหภูมิเพื่อเปรียบเทียบกับข้อมูลที่เหลือ หากข้อมูลเล็กกว่าอุณหภูมิปรากฏขึ้นให้ใช้แทนข้อมูลต้นฉบับในอุณหภูมิ สำหรับรายละเอียดที่อ้างถึงตัวอย่างรหัสด้านล่างฉันเชื่อว่าคุณได้เรียนรู้สำหรับคำสั่งวนรอบก่อนที่จะเรียนรู้ที่จะเรียงลำดับ ด้วยวิธีนี้มันจะเข้าใจได้ง่ายโดยเฉพาะที่นี่
ตัวอย่างรหัส:
// เลือกเรียงลำดับการเลือกคลาสสาธารณะ {โมฆะสาธารณะคงที่หลัก (สตริง [] args) {int [] arr = {1,3,2,45,65,33,12}; System.out.println ("ก่อนการแลกเปลี่ยน:"); สำหรับ (int num: arr) {system.out.print (num+""); } // เลือกการเพิ่มประสิทธิภาพของการเรียงลำดับสำหรับ (int i = 0; i <arr.length - 1; i ++) {// เรียงลำดับคำสั่ง i -th int k = i; สำหรับ (int j = k+1; j <arr.length; j ++) {// เลือกบันทึกที่เล็กที่สุดถ้า (arr [j] <arr [k]) {k = j; // หมายเหตุตำแหน่งของค่าต่ำสุดที่พบจนถึงตอนนี้}} // หลังจากสิ้นสุดลูปด้านในนั่นคือหลังจากค้นหาจำนวนขั้นต่ำของลูปนี้แล้วแลกเปลี่ยนถ้า (i! = k) {// swap a [i] และ a [k] int temp = arr [i]; arr [i] = arr [k]; arr [k] = อุณหภูมิ; }} system.out.println (); System.out.println ("หลังการแลกเปลี่ยน:"); สำหรับ (int num: arr) {system.out.print (num+""); -ภาพหน้าจอของผลการทำงาน:
เลือกความซับซ้อนของเวลาของการเรียงลำดับ: จำนวนการเปรียบเทียบการเลือกแบบง่าย ๆ ไม่มีอะไรเกี่ยวข้องกับการเรียงลำดับเริ่มต้นของลำดับ สมมติว่าลำดับที่จะจัดเรียงมีองค์ประกอบ n จำนวนการเปรียบเทียบจะเป็น n (n-1)/2 เสมอ จำนวนการเคลื่อนไหวเกี่ยวข้องกับการเรียงลำดับเริ่มต้นของลำดับ เมื่อลำดับเป็นบวกจำนวนการเคลื่อนไหวคือน้อยที่สุดซึ่งก็คือ 0 เมื่อลำดับถูกจัดลำดับแบบผกผันการเคลื่อนไหวส่วนใหญ่คือ 3N (N-1)/2
ดังนั้นโดยสรุปความซับซ้อนของเวลาของการเรียงลำดับง่ายคือ o (n2)