有什么快速挑出1024个数据中最大五个数的算法？或者快速排序算法。

hackthree · 发表于 2011-11-16 08:51:38

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

.titrwh · 发表于 2011-11-16 08:52:56

只会冒泡法排序。

hackthree · 发表于 2011-11-16 08:54:08

回复【1楼】.titrwh 灰机
-----------------------------------------------------------------------

冒泡的话，排1024个数据花的时间太长了。。

lllaaa · 发表于 2011-11-16 08:58:17

找最大的数要排序做啥。。。。

冒泡排序也是不停的再找最大数。

比较就完了。用个临时变量存放最大数。遇到大的就放进去。扫一遍就得到了，

gzhuli · 发表于 2011-11-16 09:00:55

如果只要前5个数据，可以做个5单元定长链表，边插边丢，甚至做个5单元数组就可以了。
话说1024个int32也才4k，怎么会那么容易把20k用完？

lllaaa · 发表于 2011-11-16 09:04:25

哦。看错了。要5个。不过也差不多。

冒泡法不做完就是了。做5次遍历

shdjdq · 发表于 2011-11-16 09:09:10

估计是想用FFT的结果，过一遍就行了。比冒泡法快好多。冒泡法也只要5遍也就行了。

hackthree · 发表于 2011-11-16 09:12:50

回复【4楼】gzhuli 咕唧霖
-----------------------------------------------------------------------

20k用完的是论坛一个朋友的那个快速排序。
我写的这个排少的还行，排大的数据就太慢了。。
就是用的5个单元的数组，边插边丢的。。
难道是我的算法有问题？
我贴上了给大伙看看

u8 max_tt[6]={25,105,125,34,70,91};
u8 max_t[2][6];

void max_test(void)
{
   u8 i,j;

   for(i=0;i<6;i++)
   {
      static u8 n=1;
      for(j=0;j<n;j++)
      {
         if(max_t[0][j]<max_tt)
         {
            u8 m;
            for(m=5;m>j;m--)
            {
               max_t[0][m]=max_t[0][m-1];
               max_t[1][m]=max_t[1][m-1];
               }
               max_t[0][j]=max_tt;
               max_t[1][j]=i;
               n=1;
               j=0;
            }
            else if(max_t[0][j]>max_tt)
               n+=1;
      }
   }
}
我这个多加了个记录数据下标的。。

XA144F · 发表于 2011-11-16 09:13:10

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

rengo · 发表于 2011-11-16 09:14:41

你这些数如果不是一次进来的，进一批挑一次

hackthree · 发表于 2011-11-16 09:15:46

回复【5楼】lllaaa
-----------------------------------------------------------------------

呵呵，还真提醒了我。
不过这个不一定是5次。。
因为假如有相同数呢？
而我只要最大不相同的5个数。。

hackthree · 发表于 2011-11-16 09:16:46

回复【6楼】shdjdq
-----------------------------------------------------------------------

哈哈，这都被你看出来了。。

.titrwh · 发表于 2011-11-16 09:18:23

uchar max[]={0,0,0,0,0};
uchar num[1024],j=0;

for(i=0;i<1024;i++)
{
if(num>max[j])
   {
   max[j]=num;
   j++;
   if(j>4)
   j=0;
}
}

随手写的，试试行不行。

hackthree · 发表于 2011-11-16 09:23:02

回复【8楼】XA144F
-----------------------------------------------------------------------

额，也是个好方法。

hackthree · 发表于 2011-11-16 09:28:16

回复【6楼】shdjdq
-----------------------------------------------------------------------

不知这过一遍得到最大五个数具体怎么过，望指导。

hackthree · 发表于 2011-11-16 09:39:07

回复【12楼】.titrwh 灰机
-----------------------------------------------------------------------

这个有问题，
不用排1024，就排8个就能看出问题。
比如下面的数据
{3,27,4,6,30,30,1,5}
排出来会丢掉27这个数吧。。
结果应该是{30,30,5,6}

.titrwh · 发表于 2011-11-16 09:41:58

确实，里面的5个数每次也应该排序。

snoopyzz · 发表于 2011-11-16 09:54:18

LS的代码明显有问题...假如result[0]如果一开始就是最大值,则后面的循环条件全都废了,你只能找出一个数来...
(我晕,我回复后,似乎少了一L....我说的LS似乎已经不存在了)
我给个正确答案吧....
===================
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

int data[1024] = { 13,1,2,3,4,5,6,7,8,9,10,11,12,13};
int max[5];

void main()
{
int n,m;
int num;
int pos = 0;
int min = data[0];
for(n=0; n<ARRAY_SIZE(max); n++)
{// 填满最初5个值,并确定搜索最小值
      num = data[n];
      max[n] = num;
      if( num<min )
      {
         min = num;
         pos = n;
      }
}
for(n=ARRAY_SIZE(max); n<ARRAY_SIZE(data); n++)
{// 最小值比较,并重新搜索
      num = data[n];
      if( num>min )
      {
         max[pos] = num;
         min = num;
         for(m=0; m<ARRAY_SIZE(max); m++)
         {
            num = max[m];
            if( num<min )
            {
                  min = num;
                  pos = m;
            }
         }
      }
}
for(n=0; n<ARRAY_SIZE(max); n++)
{// 显示结果
      printf("%d\n",max[n]);
}
}

johnwjl · 发表于 2011-11-16 09:56:22

ls 的应该不行，举个特例：最大的数在data[0]，结果为result[0]为最大数，result数组其他值为0.

.titrwh · 发表于 2011-11-16 09:57:21

回复【19楼】snoopyzz
-----------------------------------------------------------------------

有人删帖了，我刚也确实看到那个程序了，和我的效果一样。

snoopyzz · 发表于 2011-11-16 09:57:37

20L....咱们说的18L....已经不存在了...你看看我的19L,是正确答案

snoopyzz · 发表于 2011-11-16 10:00:17

我在19L给的是正确答案...而且优化过...正常的比较是 5*1024次...或者1024*5次...
我这种记录下最小值和位置...会明显减少比较次数...只有原数组取出的数,小于已知最大5个数中最小值时,才替换掉并重新搜索最小值...

原理就是这样...也话有更简单的算法...但这个已经足够了...

albert_w · 发表于 2011-11-16 10:09:51

这个问题.... 一遍搞定吧,跑5遍对不起cpu

保证top5是有序的就可以了,每个数据先pk5弟,赢了就找个位置,挤掉五弟

johnwjl · 发表于 2011-11-16 10:12:40

19L考虑一下int data[1024] = { 13,13,2,3,4,5,6,7,8,9,10,11,12}这种情况，可以得到正确答案吗？

laujc · 发表于 2011-11-16 10:18:50

我给个思路,你先设置5个变量,比如Temp[5];
存放1024的前5个数,然后回复【4楼】gzhuli 咕唧霖
如果只要前5个数据，可以做个5单元定长链表，边插边丢，甚至做个5单元数组就可以了。
话说1024个int32也才4k，怎么会那么容易把20k用完？
-----------------------------------------------------------------------

攒同.
不过如果换成5个指针,第一次遍历,指针1指向最大的.
第二次,指针2 指向除指针1指向数值外最大的.
第三次,指针3指向除指针1,2指向数值外最大的.
第四次,
第五次.
这样也非常快速的.而且运行时间不会随数据量增加而增加太多.

snoopyzz · 发表于 2011-11-16 10:20:54

回复【26楼】johnwjl
19l考虑一下int data[1024] = { 13,13,2,3,4,5,6,7,8,9,10,11,12}这种情况，可以得到正确答案吗？

-----------------------------------------------------------------------

经测试没问题呀...

snower · 发表于 2011-11-16 10:54:19

先声明一下，18L的帖子是我自己删除的，因为帖子发出去之后就发现有问题，所以自己删除了
重新修改了代码
for(int i = 0; i < 1024; ++i)
{
      if(data > result[4])
      {
         for(int j = 0; j < 5; ++j)
         {
            if(data == result[j])
            {
                  goto do_next;
            }
            if(data > result[j])
            {
                  {
                     for(int k = 4; k > j; --k)
                     {
                        result[k] = result[k - 1];
                     }
                  }
                  result[j] = data;
                  goto do_next;
            }
         }
      }
do_next:
      ;
}

本来想把goto优化掉，但是后来发现实在有难度，所以就这样了
LS的代码确实有问题，因为LZ说明结果要去重，而LS的代码，13会被重复输出
重新贴出的这段代码经过调试和测试，应该能满足LZ的要求了，而且不占用额外的内存空间，比较次数也尽量减到了最少
同时输出结果是按照降序排列的

laujc · 发表于 2011-11-16 11:44:09

回复【29楼】snower
-----------------------------------------------------------------------

goto do_next

是不是可以用break或continue ?

snoopyzz · 发表于 2011-11-16 11:52:31

回复【29楼】snower
-----------------------------------------------------------------------

13出现两次,当然应该输出两次...难道不是吗?

LZ说的是最大的5个数...而不是最大的5个不同的数

NJ8888 · 发表于 2011-11-16 12:34:40

如果数据输入时能来得及处理,边输入边二分法排序建立链表,这样1024输入完毕,根据链表就可以了

snower · 发表于 2011-11-16 13:02:18

回复【31楼】snoopyzz
回复【29楼】snower
-----------------------------------------------------------------------
13出现两次,当然应该输出两次...难道不是吗?
lz说的是最大的5个数...而不是最大的5个不同的数
-----------------------------------------------------------------------

回复【10楼】hackthree  黑客的小三
回复【5楼】lllaaa
-----------------------------------------------------------------------
呵呵，还真提醒了我。
不过这个不一定是5次。。
因为假如有相同数呢？
而我只要最大不相同的5个数。。
-----------------------------------------------------------------------

10楼是LZ的追加需求 :)

snoopyzz · 发表于 2011-11-16 13:16:20

回复【33楼】snower
-----------------------------------------------------------------------

如果LZ要求是5个不同的最大数的话...那么还需要判断数据是否能满足这个条件...即统计出最后有哪几个最大的不同的数...

否则,数据大部分相同时,无法得到5个不同的数...

hackthree · 发表于 2011-11-16 13:42:29

回复【8楼】XA144F
-----------------------------------------------------------------------

呵呵，谢谢楼上所有的朋友。。
用了8楼XA144F的思路。
取每次比较的最大值，然后清零最大值。
5次下来就可以。。
当然，这里没有考虑相同值。
考虑相同值也不难，只需加个判断就能搞定

应该是执行了5*1024步吧。

思路代码如下。没用1024。用的6。

u8 max_tt[6]={25,105,125,105,70,91};
u8 max_t[2][6];

void max_test1(void)
{
u8 max_ttt[6];
u8 i,j,k,m;
for(i=0;i<6;i++)       //赋值给暂存量max_ttt[]
{
      max_ttt=max_tt;
}
for(k=0;k<6;k++)       //要挑的最大数据个数
{
      for(j=0;j<6;j++)//要挑的数据总数
      {
         if(max_t[0][k]<max_ttt[j])
         {
               max_t[0][k]=max_ttt[j];
               max_t[1][k]=j;
            }
      }
      max_ttt[max_t[1][k]]=0;//清零最大值
   }
}

用起来还行。。

hackthree · 发表于 2011-11-16 14:01:07

回复【29楼】snower
-----------------------------------------------------------------------

和我7楼的代码应该是一个思路。
这个貌似执行的次数太多。

eggcar · 发表于 2011-11-16 14:16:51

亲，总共撑破天用不了o(n*m)的复杂度- -!这有啥好纠结的……

况且考虑最坏情况也达不到o(nm)的复杂度，具体算概率还挺麻烦的。最好的情况是o(n)。

snoopyzz · 发表于 2011-11-16 14:20:55

回复【36楼】hackthree 黑客的小三
-----------------------------------------------------------------------

不考虑相同值的话,你会发现我在19L的代码是最快的...

hackthree · 发表于 2011-11-16 14:31:23

回复【38楼】snoopyzz
-----------------------------------------------------------------------

谢朋友，我来试试看。

hackthree · 发表于 2011-11-16 14:33:14

回复【37楼】eggcar 八号机
-----------------------------------------------------------------------

哈哈，能省当然想省，能快当然想快啦。

eggcar · 发表于 2011-11-16 14:40:24

咳，这么简单的算法，没看楼上的，不知道有没有重复的

第一步取前五个数从大到小排序，存入临时数组
然后每次取后面一个数，先与数组中最大的数比较，如果比这个数大，就删掉数组中最小的数把当前数存入。如果比这个数小，则比较第二大的数，以此类推。
over
当m<<n时这就是最优算法了。当然插入的时候也可以二分插入，性能优化不大，代码量增加不少，不划算。

XA144F · 发表于 2011-11-16 14:44:14

如果遇到有相同值得情况，那就要执行2*5*1024次了。

第一次扫描找到最大值，第二次扫描将和最大值相同的数字清零。然后重复操作。

eggcar · 发表于 2011-11-16 14:59:44

回复【42楼】XA144F
如果遇到有相同值得情况，那就要执行2*5*1024次了。

第一次扫描找到最大值，第二次扫描将和最大值相同的数字清零。然后重复操作。
-----------------------------------------------------------------------

亲，这和相同值有什么关系。。。
上面算法用链表实现的话几乎不耗时间。

ele_eye · 发表于 2011-11-16 15:05:36

回复【12楼】.titrwh 灰机

接你的程序修改下应该就可以了，没试过，直接在浏览器里面敲的代码

uchar max[]={0,0,0,0,0};
uchar num[1024]

for(u16 i=0;i<1024;i++)
{
  for(u8 j=0;j<5;j++)
  {
   if(num>max[j])
   {
      max[j]=num;
      for (u8 k=j; k<5; k++)
      {
      max[k]=max[j];
      }
      break;
   }
  }
}

hackthree · 发表于 2011-11-16 16:29:09

回复【19楼】snoopyzz
-----------------------------------------------------------------------

STM32F103VB上，大于400个数就死掉了。。

而且5个数排序也有误。

难道是我哪边copy错了？

运行结果。
13,13,10,11,12

uurun · 发表于 2011-11-16 16:43:57

先取前五个数排一下序然后往后一直比较比方说abxde五个数从大到校排列回复【44楼】ele_eye
-----------------------------------------------------------------------

这个效率不高吧太占时间了最坏的情况要比较5*1024次是不是?

hackthree · 发表于 2011-11-16 17:07:32

其实，思路大家都对。
但是，这个速度不光要考虑比较的次数。。
还好考虑数据不停排序时的左移右移的次数。。
用5个数的数组，先排序再不停比较扔掉最小数。
这里面数据的移动也占用不少时间。
望拍砖

lang1437 · 发表于 2011-11-16 17:11:03

回头也琢磨下！

o0pingu0o · 发表于 2011-11-16 17:15:08

mark

dzmcs · 发表于 2011-11-16 17:23:20

位排序不知道如何呢
不用移动，1024次操作
空间换时间吧

eggcar · 发表于 2011-11-16 17:23:54

回复【47楼】hackthree 黑客的小三
其实，思路大家都对。
但是，这个速度不光要考虑比较的次数。。
还好考虑数据不停排序时的左移右移的次数。。
用5个数的数组，先排序再不停比较扔掉最小数。
这里面数据的移动也占用不少时间。
望拍砖

-----------------------------------------------------------------------

亲，你都不看回复的吗！不是说了用链表了吗。。。

snoopyzz · 发表于 2011-11-17 08:44:16

回复【45楼】hackthree 黑客的小三
回复【19楼】snoopyzz
-----------------------------------------------------------------------
stm32f103vb上，大于400个数就死掉了。。

而且5个数排序也有误。
难道是我哪边copy错了？
运行结果。
13,13,10,11,12
-----------------------------------------------------------------------

我并没有最大的5个数进行排序,需要的话,可以在程序最后加上...肯定比边排序边搜索要快的多...
另外...我在电脑上测试1024个数...没有问题...

王森 · 发表于 2014-9-12 14:22:09

学习了！

qq915412051 · 发表于 2014-9-12 17:03:56

有空看看

szyxyhy · 发表于 2014-9-13 12:23:09

本帖最后由 szyxyhy 于 2014-9-13 14:26 编辑

说一下我的思路，应该比他们的要快。

首先数组载入前5个数。
执行一个函数，内容是让指针指向5个数中最小的数，同时返回5个数中最小数数值。
最小数与第6个数比较。
如果第6个数比最小数大，替换指针指向的数，同时执行前面的函数。
如果第6个数比最小数，继续比较第7个数。直到最后。

完成之后有需要的话可以给5个数冒个泡。

有什么快速挑出1024个数据中最大五个数的算法？或者快速排序算法。

阿莫论坛20周年了！感谢大家的支持与爱护！！