[讨论贴，米有分]我所知的算法问题1

Question

首先，排序的最好的平均复杂度，不是O(nlogn)而是O(n), 比如对26个字母的出现频率的排序。但是，这样的排序是有前提的。以本题为例，如果这些数的取值范围有限（最好是个数较小,且连续）的情况下，可以达到O(n)。假设，取值范围是[0, m)int[] x = new int[m];for (int i = 0; i < n.length; i++) {
  x[n[i]]++;
}先统计每个可选值的出现次数，然后根据x里面储存的出现次数，找到前k个数

Answer 1

但是，如果是对任意数字的排序，查找前K个数字的话，我暂时想不出O(n)的算法

Answer 2

可能题目说的有误差？
n个各不相同的数，找到从大到小（或从小到大）前K个数，并非是按出现次数排（各不相同的话，每个只出现一次阿，所以明显不可能）但是shine333(enihs)
快速排序平均复杂度才是O(nlogn)
相信也知道，讨论最好情况没什么意义。我的思路是基本依据分治找第K大的数字的算法
继续继续，希望看到更多的发言

Answer 3

我说的上面O(n), 在像26个字母出现频率，100个员工的生产量这种特定排序的情况下，最好最坏平均复杂度都是O(n)的，而不单单是最好复杂度。这种算法的复杂度永远是O(n),但是很少用它的原因，就是因为在存储空间上，要求太高了。但是时间复杂度绝对是最简单的，因为不可能有比O(n)更低的吧。还有这个算法和每个候选者的最多出现次数无关。此外，我非常同意
>相信也知道，讨论最好情况没什么意义。
这句话，但是，我想补充一点，讨论最坏情况，是有意义的，因为这个牵涉到了算法的稳定性。>依据分治找第K大的数字的算法
Thinking...

Answer 4

恩
不过抱歉，可能这种算法就是找第K大的算法。（还好，题目，结论，复杂度都没有错）
现在我的做法是平均下复杂度O(n)，改进一下可以做到最坏情况O(n)还是分治法
数组a[p:r]划分成2个子数组a[p:i]和a[i+1:r]
使得所有a[p:i]中的所有元素都小于等于a[i]而a[i+1:r]所有元素都大于a[i]
如果此时k>i，那么第k大个元素落在a[i+1:r]中
如果k<i,那么此时第k大个元素落在a[p:i]中
然后就可以递归调用
假设函数为select(int[] a,int p,int r,int k);
a[]：数组，p：起始位置,r:终止位置,k：第k个
例如，当k大个元素落在a[p:i]中时，就变成调用select(int a[],p,i,k-i);
当找到第k个的时候，只要返回下标就可以了划分基准：可以用随机数划分或者a[p]划分，那么就是平均复杂度O(n)
改进后可以在最坏情况下做到O(n)，不过好像这个划分有些复杂，暂时我不是很理解。我只能依据快速排序的做法做到这样划分。OK，接下来我应该会在写一道我暂时没有很清晰思路的题目。ps:我手上有一些比较多的算法题目，但是大概只做出来一半左右。
+u+u，如果能抛砖引玉更好了