hash表可用于排序整数现在有一个需求,已知有百万级的数据例如2019年全国高考理科学生的分数,需要进行一个排序工作请设计一个代码要求在最短的时间里进行排序。
囧希表排序使用数组的下表对正整数排序。规定hash表长度需要超过最大待排序的数字时间复杂度为o(表长+n) n为元素个数。
回到实际案例理科高考分数最高位750,那么表长度为750假设有800w的考生,最后的时间复杂度为o(n)
总结:哈希表排序使用范围是有一定数据规模,并且待排序的數据都要在[0, x]其中x为有限范围内的数据,否则会造成hash表申请空间过大效率降低的情况。