Jac*_*ale 12 sorting algorithm data-structures
这不是我学校的家庭作业.这是我自己的家庭作业,我是自学算法.
在算法设计手册中,有这样的消费税
4-25假设数组A [1..n]只有{1,...的数字...,n ^ 2}但是这些数字的最多日志log n出现了.设计一种算法,将A排序在一个基本上小于O(n log n)的范围内.
我有两种方法:
第一种方法:
基本上我想对这个问题进行计数.我可以先扫描整个数组(O(N))并将所有不同的数字放入loglogN大小数组(int [] K).
然后应用计数排序.但是,在设置计数数组(int [] C)时,我不需要将其大小设置为N ^ 2,而是将大小设置为loglogN.
但是这样,当计算每个不同数字的频率时,我必须扫描数组K以获得该元素的索引(O(NloglogN),然后更新数组C.
第二种方法:
同样,我必须扫描整个数组以获得具有大小loglogN的不同数字数组K.
然后我只是做了一种类似的快速排序,但是分区是基于K数组的中位数(即,每次转轴是K数组的一个元素),递归地.
我认为这种方法最好用O(NlogloglogN).
我对吗？还是有更好的解决方案？
算法设计手册中存在类似的消息,例如
4-22显示1到k范围内的n个正整数可以在O(n log k)时间内排序.有趣的情况是k << n.
4-23我们寻求对具有许多重复的n个整数的序列S进行排序,使得S中不同整数的数量为O(log n).给出O(n log log n)最坏情况时间算法来对这些序列进行排序.
但基本上对于所有这些消除,我的直觉总是考虑计数排序,因为我们可以知道元素的范围,并且范围与整个数组的长度相比足够短.但是经过更深入的思考,我猜这些消费者正在寻找的是第二种方法,对吧？
谢谢
我们可以创建一个哈希映射,将每个元素存储为键,将其频率存储为值.
log(n)*log(log(n))使用任何排序算法对该地图进行时间排序即(klogk).
现在扫描哈希映射并将元素添加到新的阵列频率次数.像这样:
total time = 2n+log(n)*log(log(n)) = O(n)