อัลกอริธึมการจัดเรียงที่เสถียรจะรักษาลำดับสัมพัทธ์ของเรคคอร์ดด้วยคีย์ที่เท่ากัน (เช่น ค่า) นั่นคือ อัลกอริธึมการจัดเรียงจะเสถียรถ้า เมื่อใดก็ตามที่มีระเบียน R และ S สองตัวที่มีคีย์เดียวกัน และ R ปรากฏขึ้นก่อน S ในรายการดั้งเดิม R จะปรากฏก่อน S ในรายการที่จัดเรียง รายการ
อัลกอริธึมการเรียงลำดับใดที่เสถียร
อัลกอริธึมการจัดเรียงทั่วไปหลายแบบมีความเสถียรโดยธรรมชาติ เช่น Merge Sort, Timsort, Counting Sort, Insertion Sort และ Bubble Sort อื่นๆ เช่น Quicksort, Heapsort และ Selection Sort นั้นไม่เสถียร
อะไรทำให้การเรียงลำดับมีเสถียรภาพ
อัลกอริธึมการจัดเรียงมีความเสถียร หากวัตถุสองชิ้นที่มีคีย์เท่ากันปรากฏในลำดับเดียวกันในเอาต์พุตที่เรียงลำดับตามที่ปรากฏในอาร์เรย์อินพุตที่จะจัดเรียง อัลกอริธึมการจัดเรียงบางอย่างมีความเสถียรโดยธรรมชาติ เช่น การเรียงลำดับการแทรก การเรียงลำดับการผสาน การเรียงลำดับฟอง เป็นต้น
อัลกอริธึมการจัดเรียงที่เสถียรพร้อมตัวอย่างคืออะไร
ตัวอย่างบางส่วนของอัลกอริธึมที่เสถียร ได้แก่ การเรียงลำดับการผสาน การเรียงลำดับการแทรก การเรียงลำดับฟอง และการเรียงลำดับต้นไม้แบบไบนารี ในขณะที่ การเรียงลำดับแบบด่วน การเรียงลำดับแบบฮีป และการเรียงลำดับการเลือกเป็นอัลกอริธึมการจัดเรียงที่ไม่เสถียร หากคุณจำคอลเล็กชัน วิธีการเรียงลำดับจากเฟรมเวิร์กการรวบรวม Java ใช้การเรียงลำดับการผสานซ้ำซึ่งเป็นอัลกอริธึมที่เสถียร
อัลกอริธึมการเรียงลำดับใดอยู่ในสถานที่และอันใดที่เสถียร
หมายเหตุ:
- การเรียงลำดับบับเบิ้ล การเรียงลำดับการแทรก และการเรียงลำดับการเลือกเป็นอัลกอริธึมการจัดเรียงแบบแทนที่ …
- การเรียงลำดับฟองและการแทรกสามารถใช้เป็นอัลกอริธึมที่เสถียรได้ แต่การเรียงลำดับการเลือกจะไม่สามารถทำได้ (หากไม่มีการแก้ไขที่สำคัญ)
- การจัดเรียงแบบผสานเป็นอัลกอริธึมที่เสถียร แต่ไม่ใช่อัลกอริธึมแบบแทนที่