อัลกอริธึมการเรียงลำดับแบบคลาสสิกสิบอันดับแรก

อัลกอริธึมการเรียงลำดับเป็นหนึ่งในอัลกอริธึมพื้นฐานที่สุดใน "โครงสร้างข้อมูลและอัลกอริธึม"

อัลกอริธึมการเรียงลำดับสามารถแบ่งออกเป็นการเรียงลำดับภายในและการเรียงลำดับภายนอก การเรียงลำดับภายในคือการเรียงลำดับบันทึกข้อมูลในหน่วยความจำ ในขณะที่การเรียงลำดับภายนอกเป็นเพราะข้อมูลที่เรียงลำดับมีขนาดใหญ่มากและไม่สามารถรองรับการบันทึกที่เรียงลำดับทั้งหมดในคราวเดียว จำเป็นต้องเข้าถึงหน่วยความจำ อัลกอริธึมการเรียงลำดับภายในทั่วไปประกอบด้วย: การเรียงลำดับการแทรก, การเรียงลำดับแบบ Hill, การเรียงลำดับการเลือก, การเรียงลำดับแบบฟอง, การเรียงลำดับแบบผสาน, การเรียงลำดับแบบด่วน, การเรียงลำดับฮีป, การเรียงลำดับ Radix เป็นต้น สรุปด้วยภาพ:

ภาพหน้าจอภาพรวมอัลกอริทึมการเรียงลำดับแบบคลาสสิกสิบอันดับแรก

เกี่ยวกับความซับซ้อนของเวลา :

การเรียงลำดับแบบสแควร์ (O(n2)) การเรียงลำดับแบบง่ายประเภทต่างๆ: การแทรกโดยตรง การเลือกโดยตรง และการเรียงลำดับแบบฟอง
ลำดับลอการิทึมเชิงเส้น (O (nlog2n)) การเรียงลำดับอย่างรวดเร็วการเรียงลำดับฮีปและการเรียงลำดับแบบผสาน
การเรียงลำดับ O(n1+§)) § เป็นค่าคงที่ระหว่าง 0 ถึง 1 เรียงเนินเขา
การเรียงลำดับเชิงเส้น (O(n)) การเรียงลำดับรัศมี นอกเหนือจากการเรียงลำดับถังและถัง

เกี่ยวกับความมั่นคง :

อัลกอริธึมการเรียงลำดับที่เสถียร: การเรียงลำดับแบบฟอง การเรียงลำดับการแทรก การเรียงลำดับแบบผสาน และการเรียงลำดับแบบ Radix

อัลกอริธึมการเรียงลำดับไม่เสถียร: การเรียงลำดับการเลือก, การเรียงลำดับอย่างรวดเร็ว, การเรียงลำดับแบบ Hill, การเรียงลำดับแบบฮีป

อภิธานศัพท์ :

n : ขนาดข้อมูล

k : จำนวน "ถัง"

In-place : ใช้หน่วยความจำคงที่และไม่ใช้หน่วยความจำเพิ่มเติม

Out-place : ใช้หน่วยความจำเพิ่มเติม

ความเสถียร : ลำดับของค่าคีย์ที่เท่ากันสองค่าหลังจากการเรียงลำดับจะเหมือนกับลำดับก่อนการเรียงลำดับ

โครงร่างเนื้อหา GitBook