有什么快速挑出1024个数据中最大五个数的算法？

只看该作者 · 2011-11-16 08:30

现在想挑出1024个数据中的最大的五个数。
自己写了个函数，效果不佳，执行的次数太多以至于遇到1024这大数据直接死掉。。
感觉，这个还是要用排序。
有看过一个论坛有位兄弟的快速排序，但是好像挺占用RAM 的，
手上的F103VB的编译过不去，大于F103VB的，也就是大于20KRAM 的都没问题。
各位有什么好的算法思路，
给咱指导指导。。

1万 · 2011-11-16 09:34

常见的排序方法有7~8种，找一本数据结构的书看看吧。

只看该作者 · 2011-11-16 09:41

其实这个根本不用排序~ 用一个五个数的数组，拿到一个数之后和这个数组里的数比较，如果大的话就把数组里最小的那个替换掉。用不了多少资源的……

1万 · 2011-11-16 10:33

同意三楼

4万 · 2011-11-16 10:45

同意四楼

1万 · 2011-11-16 10:57

3楼的方法不错，占用资源最少，但速度不一定是最快。

只看该作者 · 2011-11-16 11:23

本帖最后由 uc_cm0 于 2011-11-16 13:18 编辑

其实这个根本不用排序~ 用一个五个数的数组，拿到一个数之后和这个数组里的数比较，如果大的话就把数组里最小的那个替换掉。用不了多少资源的…… ...
grissiom 发表于 2011-11-16 09:41

9楼正解。

1万 · 2011-11-16 11:39

用一个五个数的数组
拿到一个数之后和这个数组里的最大的数比较，如果大的话就把数组里最小的数删除掉，新的最大的数加入到数组。
uc_cm0 发表于 2011-11-16 11:23

这个办法觉得更好些，但不完备。除了需要跟这个数组里的最大的数比较，还需要这个数组里的最小的数比较

1万 · 2011-11-16 12:20

应该是先比较最小的数, 以保证进入数组的门槛. 然后再嵌入到数组中比它大的数后面. 后面的数依次移出.
可以在比较的时候,就进行移动的.

1万 · 2011-11-16 13:12

常见的排序方法有7~8种，找一本数据结构的书看看吧

看过用过，不过又忘记了。
知道有相应算法和出处，用时再记了。

只看该作者 · 2011-11-16 13:59

谢各位。
现在用的是一次扫描数组，将最大的数据提取出来，并将最大数所在位置设置为0，然后重复操作。

只看该作者 · 2011-11-16 14:02

3# grissiom

好像和我之前的思路有点相同，但是也有点不同，我再琢磨琢磨。。:lol

只看该作者 · 2011-11-16 14:03

9楼正解。
uc_cm0 发表于 2011-11-16 11:23

这位兄弟未卜先知哈。。
7楼就能预见到9楼了。。:lol

只看该作者 · 2011-11-16 14:06

应该是先比较最小的数, 以保证进入数组的门槛. 然后再嵌入到数组中比它大的数后面. 后面的数依次移出.
可以在比较的时候,就进行移动的.
airwill 发表于 2011-11-16 12:20

是的，比较最大的数的话，有的情况会漏掉一些数。

只看该作者 · 2011-11-16 15:22

找本数据结构的书看看吧。

只看该作者 · 2011-11-16 16:07

要是保证速度的话，要使那五个数的数组是被排序的，这样最多三次比较就能知道新的大数需要放在哪里。五个数组的排序，随便哪个算法就够用了……

具体的代码就不贴了吧……

排序算法的最快时间复杂度是 O(nlogn)。五个数数组扫描一遍的算法时间复杂度是 O(n)。因为避免了不必要的排序(不用对后面的一千多个数进行排序)，所以会快些～

2万 · 2011-11-16 16:24

1 建立一个5个数的数组，记作dst[5]
2 从1024数组中拷贝前5个数据到dst
3 标记出dst数组中最小数据的位置，记作pos
4 从1024数组中第6个数开始遍历，数据记作src[i]
5 如果src[i]小于dst[pos]则丢弃，否则用src[i]覆盖dst[pos]
6 扫描dst，依据step3刷新pos值
7 直到遍历结束
8 对dst数组冒泡排序
9 大功告成