Counting sort is a very time-effici

Counting sort is a very time-efficient (and somewhat space-inefficient) algorithm for sorting that avoids comparisons and exploits the O(1)O(1) time insertions and lookups in an array.

The idea is simple: if you're sorting integers and you know they all fall in the range 1..1001..100, you can generate a sorted array this way:

Allocate an array numsToCounts where the indices represent numbers from our input array and the values represent how many times the index number appears. Start each value at 0.
In one pass of the input array, update numsToCounts as you go, so that at the end the values in numsToCounts are correct.
Allocate an array sortedArray where we'll store our sorted numbers.
In one in-order pass of numsToCounts put each number, the correct number of times, into sortedArray.

ผลลัพธ์ (ไทย) 1:

การนับเรียงลำดับมีการมากเวลาที่มีประสิทธิภาพ (และพื้นที่ค่อนข้างต่ำ) อัลกอริทึมสำหรับการเรียงลำดับที่เพื่อหลีกเลี่ยงการเปรียบเทียบ และหาประโยชน์แทรกเวลา O(1)O(1) และค้นหาในอาร์เรย์ความคิดเรียบง่าย: ถ้าคุณจะเรียงลำดับจำนวนเต็ม และคุณรู้ว่า พวกเขาทั้งหมดตกอยู่ในช่วง 1..1001..100 คุณสามารถสร้างแถวลำดับการเรียงลำดับด้วยวิธีนี้:จัดสรร numsToCounts การอาร์เรย์ที่ดัชนีแทนตัวเลขจากอาร์เรย์ของเราป้อนข้อมูล และค่าแสดงจำนวนครั้งที่ปรากฏหมายเลขดัชนี เริ่มต้นแต่ละค่าที่ 0ในอาร์เรย์ป้อนข้อมูล อัพเด numsToCounts คุณไป เพื่อให้จบ ค่าใน numsToCounts ถูกต้องจัดสรร sortedArray อาร์เรย์ตัวที่เราจะเก็บหมายเลขของเราเรียงลำดับในในการสั่งซื้อของ numsToCounts ใส่แต่ละหมายเลข หมายเลขที่ถูกต้องของเวลา sortedArray

ผลลัพธ์ (ไทย) 2:

นับเรียงเป็นขั้นตอนวิธีมากเวลาอย่างมีประสิทธิภาพ (และค่อนข้างพื้นที่ไม่มีประสิทธิภาพ) สำหรับการจัดเรียงที่หลีกเลี่ยงการเปรียบเทียบและการใช้ประโยชน์จาก O นี้ (1) O (1) การแทรกเวลาและ lookups ในอาร์เรย์.

ความคิดง่ายๆคือ: ถ้าคุณกำลังคัดแยก จำนวนเต็มและคุณรู้ว่าพวกเขาตกอยู่ในช่วง 1..1001..100 คุณสามารถสร้างอาร์เรย์เรียงวิธีนี้:

จัดสรร numsToCounts อาร์เรย์ที่ดัชนีแทนตัวเลขจากอาร์เรย์ป้อนข้อมูลของเราและค่านิยมแทนจำนวนครั้งที่หมายเลขดัชนี ปรากฏ เริ่มต้นแต่ละค่าที่ 0
ในหนึ่งผ่านการป้อนข้อมูลของอาร์เรย์การปรับปรุง numsToCounts ที่คุณไปเพื่อที่ว่าในตอนท้ายค่าใน numsToCounts ถูกต้อง.
จัดสรรอาร์เรย์ sortedArray ที่เราจะเก็บหมายเลขเรียงลำดับของเรา.
หนึ่งในการสั่งซื้อ ผ่านของ numsToCounts ใส่หมายเลขแต่ละหมายเลขที่ถูกต้องครั้งเข้า sortedArray

ผลลัพธ์ (ไทย) 3:

นับเรียงเป็นมากเวลาที่มีประสิทธิภาพ ( และค่อนข้างพื้นที่ไม่มีประสิทธิภาพ ) ขั้นตอนวิธีการจัดเรียงที่หลีกเลี่ยงการเปรียบเทียบและใช้ประโยชน์จาก O ( 1 ) O ( 1 ) และเวลาใหม่ การค้นหาในอาร์เรย์แนวคิดง่าย : ถ้าคุณเรียงลำดับจำนวนเต็มและคุณรู้ว่าพวกเขาทั้งหมดอยู่ในช่วง 1 . . . . . . . 1 . . . 100 , คุณสามารถสร้างอาร์เรย์แบบจัดเรียงด้วยวิธีนี้ :แบ่งอาร์เรย์ numstocounts ที่ดัชนีแทนตัวเลขจากเรย์ใส่ของเราและค่าแสดงกี่ครั้งเลขดัชนีที่ปรากฏ เริ่มต้นแต่ละค่า 0ในหนึ่งผ่านอาร์เรย์ของข้อมูลการปรับปรุง numstocounts ตามที่คุณไป ดังนั้นเมื่อสิ้นสุด numstocounts ค่าถูกต้องแบ่งอาร์เรย์ sortedarray ที่เราจะร้านเรียงหมายเลขในหนึ่งในการสั่งซื้อผ่าน numstocounts ใส่แต่ละหมายเลขที่ถูกต้องจำนวนครั้ง ใน sortedarray .