JONY

计数排序(Count Sort) 计数排序是最简单的基于哈希表的排序算法，常用的排序算法是比较排序，但基于哈希表的排序一般都属于非比较排序。这类排序算法的特点是牺牲空间来换取更低的时间复杂度，这个时间复杂度甚至低于比较排序的理论极限\(O(n\lg n)\)。但这类排序对输入的数有限制、并且可能会占用相当多的空间，所以应用并不如比较排序广。 计数排序要求输入的每个数都必须是整数，算法流程是先创建空哈希表，然后遍历输入找到最大值\(max\)和最小值\(min\)，再在哈希表中依次插入关键字\(min, min+1,…,max\)并让每个关键字关联一个值用来表示“关键字在输入中的个数”，所以值初始都为0。然后遍历输入并在哈希表统计各数的出现次数，最后根据\(max\)和\(min\)按\(min,… 阅读全文