100W个随机数据里面找出最大的5个

lovfreebsd

生成100w随机数

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. main()
   
5. {
   
6.   FILE *fp;
   
7.   long get;
   
8.   long i=0;
   
9.   srand((unsigned)time(NULL));
   
10.   fp = fopen("srand.txt","w");
    
11.   for(i=0;i<1000000;i++)
    
12.    {
    
13.     get = rand();
    
14.     fprintf(fp,"%d\n",get);
    
15.     }
    
16.    fclose(fp);
    
17. }

复制代码

读入数据

1. 
   
2. #include<stdio.h>
   
3. void  sort( ******);
   
4. main()
   
5. {
   
6.   int t;
   
7.   char *s;
   
8.   FILE *fp;
   
9.   s = malloc(100);
   
10.   fp = fopen("srand.txt","r");
    
11.   while(!feof(fp))
    
12.    {
    
13.     fgets(s,100,fp);
    
14.     t = atoi(s);
    
15.     sort(***);
    
16.    }
    
17. free(s);
    
18. fclose(fp);
    
19. }
    

复制代码

到选用算法的时候就特别郁闷。难道我弄一个100w的数组来用吗？

cugb_cat

只用一个5个元素大的数组就行了，不用排序。

lovfreebsd

以前有朋友也这样建议过我。做一个五个数的数组，可以先取前5个到数组里，对它们进行排序。然后取6到100w的数据跟这个五位的数组比较。这个数组也可以优化一下，就是设立前中后指针。分别对应小中大的数。如果取出来的数比最小的还小，就抛弃数组里最大的那个数。如果大于最大的数，可以直接不管。
这好几天都在想这个问题。我看好多实现都是用指针。总是被绕的晕乎乎的。

holyfire

int sort(int in_arr[], int in_size, int out_arr[], int out_size)
{
        int i = 0;
        int cur_size = 0;
        for ( ; i < in_size; ++i) {
                int j = 0;
                for ( ; j < cur_size; ++j) {
                        if (in_arr >= out_arr[j]) {
                                int move_count = cur_size - j;
                                if (out_size == cur_size) {
                                        move_count--;
                                }
                                else {
                                        cur_size++;
                                }
                                memmove(out_arr + j + 1, out_arr + j, move_count * sizeof (int));
                                out_arr[j] = in_arr;
                                break;
                        }
                }
                if (j == cur_size && cur_size < out_size) {
                        out_arr[cur_size++] = in_arr;
                }
        }

        return cur_size;
}

lovfreebsd

刚在学校的时候学过c，但都是毛皮。
holyfire  写的for循环，很有特点
int i = 0;
int cur_size = 0;
for ( ; i < in_size; ++i)

int j = 0;
for ( ; j < cur_size; ++j)
不知道这种编程的风格是大家都有的，还是holyfire的个人特色！:wink:

欢迎大家拿出你的风格，小小的show一下。
我先谢谢大家的指教了。

[ 本帖最后由 lovfreebsd 于 2007-11-14 17:27 编辑 ]

scutan

使用堆. 堆只需要五个元素就行. 然后每来一个数, 将其压入堆中, 然后将最小的数去掉就可以了.

lovfreebsd

原帖由 cugb_cat 于 2007-11-14 16:09 发表
只用一个5个元素大的数组就行了，不用排序。

while(!feof(fp))
  {
      fgets(s,100,fp);
      t = atoi(s);
      sort(**);
}


这个地方不知道怎么把取出来的数(t)前5个赋值给一个5位的数组。我老是一拿就是一全拿.
麻烦大家了

[ 本帖最后由 lovfreebsd 于 2007-11-16 11:29 编辑 ]

lovfreebsd

大家感兴趣的话,可以写写实现代码试试.

  while(!feof(fp))
   {
    fgets(s,100,fp);
    t = atoi(s);
    ………………
   }

这里我想拿出五个数存到数组里。结果怎么着都不行，

[ 本帖最后由 lovfreebsd 于 2007-11-16 16:56 编辑 ]

hibernator

链表的效率应该比数组要好。

这题目说白了是用深度为5的栈可以解决的问题，如果用数组，数据移动次数太多了。不过，5个元素还不是很明显。

lenovo

原帖由 lovfreebsd 于 2007-11-16 11:32 发表
大家感兴趣的话,可以写写实现代码试试.

  while(!feof(fp))
   {
    fgets(s,100,fp);
    t = atoi(s);
    ………………
   }

这里我想拿出五个数存到数组里。结果怎么着都不行，

使用fscanf。