คำนำ: หัวข้อของโครงสร้างข้อมูล Java และอัลกอริทึมจะได้รับการปรับปรุงเป็นครั้งคราว ผู้อ่านสามารถดูแลได้ บทความนี้เริ่มต้นด้วยอัลกอริทึมการเรียงลำดับที่ง่ายที่สุด - การเรียงลำดับของถังและวิเคราะห์แนวคิดการใช้งานการใช้งานรหัสลักษณะประสิทธิภาพและสถานการณ์ที่ใช้งานได้ของการเรียงลำดับของถัง
0. ดัชนีอัลกอริทึมการเรียงลำดับอื่น ๆ
//www.vevb.com/article/120879.htm
1. แนวคิดการเรียงลำดับถัง
ตัวอย่างง่ายๆ:
การเรียงลำดับคะแนนการทดสอบภาษาอังกฤษ 6 คน (1 ~ 10 คะแนน) หากคะแนนคือ [6, 5, 8, 8, 10, 9] ความคิดในการเรียงลำดับด้วยถังคือการเตรียม 10 ถังตัวเลขคือ 1 ~ 10 ตามลำดับและคะแนนจะถูกวางไว้ในถังที่สอดคล้องกันเช่น 6 คะแนนลงในถังหมายเลข 6 นี่คือแนวคิดพื้นฐานของการเรียงลำดับถัง
อันที่จริงนี่เป็นเพียงเวอร์ชันที่เรียบง่าย แค่คิดว่าถ้าช่วงขององค์ประกอบที่จะจัดเรียงนั้นค่อนข้างใหญ่เช่น 1 ~ 10,000 คุณต้องการ 10,000 ถังหรือไม่? ในความเป็นจริงในกรณีนี้องค์ประกอบหนึ่งไม่ได้ถูกวางไว้ในถังเสมอไป แต่หลายครั้งที่มีหลายองค์ประกอบถูกวางไว้ในถัง ในความเป็นจริงการเรียงลำดับถังจริงและรายการแฮชมีหลักการเดียวกัน
ในการเรียงลำดับจริงองค์ประกอบในแต่ละถังมักจะเรียงลำดับโดยใช้อัลกอริทึมการเรียงลำดับอื่น ๆ ดังนั้นบ่อยครั้งที่ใช้การเรียงลำดับถังรวมกับอัลกอริทึมการเรียงลำดับอื่น ๆ
2. รหัสการเรียงลำดับถัง
หลังจากวิเคราะห์แนวคิดของการเรียงลำดับถังคุณต้องทราบช่วงขององค์ประกอบที่จะเรียงลำดับก่อน ตัวอย่างข้างต้นเป็นตัวอย่างประกาศอาร์เรย์ที่มีความยาว 10 เป็น 10 ถังแล้วใส่ผลลัพธ์ทีละรายการลงในถังค่าของถังคือ +1 และในที่สุดก็ส่งออกอาร์เรย์ตัวห้อยตามลำดับย้อนกลับ ค่าของแต่ละตำแหน่งของอาร์เรย์จะถูกส่งออกหลายครั้งเพื่อให้สามารถเรียงลำดับถังพื้นฐานได้
BucketSort ระดับสาธารณะ {Private int [] buckets; INT ส่วนตัว [] อาร์เรย์; Public Bucketsort (ช่วง int, int [] array) {this.buckets = new int [ช่วง]; this.array = Array; } /*การเรียงลำดับ* / public void sort () {if (array! = null && array.length> 1) {สำหรับ (int i = 0; i <array.length; i ++) {buckets [array [i]] ++; }}}/*เอาต์พุตการเรียงลำดับ*/การจัดเรียงโมฆะสาธารณะ () {// ข้อมูลเอาต์พุตย้อนกลับสำหรับ (int i = buckets.length-1; i> = 0; i-) {สำหรับ (int j = 0; j <buckets [i]; j ++) -รหัสทดสอบ:
คลาสสาธารณะ sorttest {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {testbucketssort (); } โมฆะแบบคงที่ส่วนตัว TestBucketSSORT () {int [] array = {5,7,3,5,4,8,6,4,1,1,2}; BucketSort BS = New BucketSort (10, Array); bs.sort (); bs.sortout (); // เอาต์พุตพิมพ์เรียงลำดับ}}3. ลักษณะการจัดเรียงของถัง
การเรียงลำดับของถังจริง ๆ แล้วต้องมีการวนซ้ำผ่านองค์ประกอบทั้งหมดที่จะจัดเรียงแล้ววางไว้ในตำแหน่งที่ระบุตามลำดับ หากมีการเพิ่มเวลาในการเรียงลำดับออกถังทั้งหมดจะต้องถูกสำรวจ ดังนั้นความซับซ้อนของเวลาของการเรียงลำดับถังคือ o (n+m), n คือจำนวนองค์ประกอบที่จะจัดเรียงและ m คือจำนวนถังนั่นคือช่วงขององค์ประกอบที่จะจัดเรียง อัลกอริทึมนี้เป็นอัลกอริทึมการเรียงลำดับที่รวดเร็วมาก แต่ความซับซ้อนเชิงพื้นที่ค่อนข้างใหญ่
เมื่อช่วงขนาดขององค์ประกอบที่จะจัดเรียงค่อนข้างใหญ่ แต่จำนวนองค์ประกอบที่จะจัดเรียงค่อนข้างเล็กขยะพื้นที่จะรุนแรงกว่า การกระจายขององค์ประกอบที่จะจัดเรียงนั้นมีความสม่ำเสมอทุกเดือนและอัตราการใช้พื้นที่ที่สูงขึ้นซึ่งเป็นของหายากจริง ๆ
ผ่านการวิเคราะห์ประสิทธิภาพข้างต้นเราสามารถได้รับลักษณะของการเรียงลำดับถัง: เร็วและง่าย แต่ในเวลาเดียวกันการใช้พื้นที่จะต่ำ เมื่อข้อมูลที่จะจัดเรียงมีขนาดใหญ่อัตราการใช้พื้นที่จะทนไม่ได้
4. การเรียงลำดับสถานการณ์ที่เกี่ยวข้อง
ตามลักษณะของการเรียงลำดับของถังการเรียงลำดับของถังมักจะใช้กับสภาพแวดล้อมเฉพาะบางอย่างเช่นช่วงข้อมูลค่อนข้าง จำกัด หรือมีข้อกำหนดเฉพาะบางประการเช่นความต้องการที่จะได้รับค่าบางอย่างผ่านการทำแผนที่แฮชอย่างรวดเร็วและจำนวนของแต่ละจำนวนจะต้องนับ แต่ทั้งหมดนี้ขึ้นอยู่กับการยืนยันขอบเขตของข้อมูล หากช่วงขอบเขตมีขนาดใหญ่เกินไปให้พิจารณาใช้อัลกอริทึมอื่น ๆ