การนับการเรียงลำดับเป็นอัลกอริทึมการเรียงลำดับที่เสถียร Count Sorting ใช้อาร์เรย์เพิ่มเติม Count_arr ซึ่งองค์ประกอบ I-th คือจำนวนองค์ประกอบที่มีค่าเท่ากับ i ในอาร์เรย์ arr ที่จะจัดเรียง จากนั้นตามอาร์เรย์ Count_arr องค์ประกอบใน arr จะถูกจัดเรียงไปยังตำแหน่งที่ถูกต้อง
แบ่งออกเป็นสี่ขั้นตอน:
1. ค้นหาองค์ประกอบที่ใหญ่ที่สุดและเล็กที่สุดในอาร์เรย์ที่จะจัดเรียง
2. สถิติจำนวนครั้งแต่ละองค์ประกอบที่มีค่าของฉันปรากฏในอาร์เรย์และบันทึกรายการ i-th ของอาร์เรย์ Count_arr
3. สะสมจำนวนทั้งหมด (เริ่มต้นจากองค์ประกอบแรกใน count_arr แต่ละรายการและรายการก่อนหน้าจะถูกเพิ่ม)
4. ย้อนกลับอาร์เรย์ดั้งเดิม: วางแต่ละองค์ประกอบ i ในรายการ count_arr (i) ของอาร์เรย์ใหม่และลบ count_arr (i) โดย 1 สำหรับแต่ละองค์ประกอบ
ตัวอย่าง:
การคัดลอกรหัสมีดังนี้:
-
* นับการเรียงลำดับเป็นอัลกอริทึมการเรียงลำดับที่ไม่ใช่การเปรียบเทียบ
* อัลกอริทึมนี้ถูกเสนอโดย Harold H. Seward ในปี 1954
* ข้อได้เปรียบคือเมื่อเรียงลำดับจำนวนเต็มภายในช่วงที่กำหนด
* ความซับซ้อนของมันคือ (n+k) (โดยที่ k คือช่วงของจำนวนเต็ม)
* เร็วกว่าอัลกอริทึมการเรียงลำดับการเปรียบเทียบใด ๆ
-
-
ฟังก์ชั่น countsort (arr, min, max) {
var i, z = 0, count = [];
สำหรับ (i = min; i <= สูงสุด; i ++) {
นับ [i] = 0;
-
สำหรับ (i = 0; i <arr.length; i ++) {
นับ [arr [i]] ++;
-
สำหรับ (i = min; i <= สูงสุด; i ++) {
ในขณะที่ (นับ [i]-> 0) {
arr [z ++] = i;
-
-
กลับ arr;
-
// ทดสอบ
var i, arr = [];
สำหรับ (i = 0; i <100; i ++) {
arr.push (math.floor (math.random () * (141)));
-
Countsort (arr, 0, 140);