UyHiP趣题：限制最苛刻的选票统计程序

the47

如果我没看错题的话，这是一个排序问题，解决这个问题的方法是，首先通过程序扫描磁带（数据源）将无序的数据进行排序，然后用数组记录票数，最后根据输入而输出。
而在最坏的情况下，最少的扫描次数也是衡量一个排序程序是否有效的标准。
排序有三种基本方法：Insert Sort,Selection Sort,Bubble Sort.后面还有Shell sort,Comb sort,quick sort等等...........
而每种排序都有自己的优点,对于楼主所说的情况，属于数据随机排列，这时候quick sort应该是最快的，但是又是最坏情况，所以说是在所有算法中，数据排列最坏的情况。（好乱= =）

好吧我承认我看错题了，这不是一个排序问题，先给一个3次的答案，前两次找人，最后算百分比，正在找2次的方法~~~~

the47

b.p.bravo 发表于 2011-3-18 08:52
插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序……
以上是刚接触算法设计必学的内部排序算 ...

翘了一天的课加熬了一晚上终于做出来了，答案应该是2.此题的关键是“票数不到百分之一不能成为候选人”，也就是说，最多只有100个候选人，那么，我只需要101个内存单位就可以了，100个候选人加1个“都不是候选人”。而这也符合O(1)的内存要求。
下面的问题是如何在N的数据中有效地利用100个单位（最后一个存0，是给输出用的），因为内存有限，所以要保证这一百个内存中存的是票数前一百的人，所以想了一个方法，在扫描数据时，将不断地存入内存，如果超过100，那么每人的票数减1，这样一来，就保证内存中的一百人是票数最多的一百人。
至于第二次扫描，算每人的票数就好了。
至于证明为什么1次不行，至今没想出来，就是觉得次数太少，没法完成必要的步骤，等待高手解答~~
睡觉去了~