首先从一个txt文件中读出数据,这个文件中有一百万个数据,要挑选其中第[N/2], [N/4], [N/8]大的数，同时给出小于等于[N/8]排列（请排序）。给出运行时间或者时间复杂度分析。

有没有高手能把源程序给我啊?

可以自己建立一个文件,里面随便输入几个数据的.

或者可以加我QQ:779264864,我把那个txt文件发给你..

先谢谢各位高手啦..

额,第一次在这里发帖,不知道可以传附件的..题目要求的文件在这个附件里面.

这么难……

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAXDATA 2000000

int  comp( const  void  * p,  const  void  * q)
{
    return ( * ( int * ) p - * ( int * ) q) ;
}

int main(int argc, char **argv)
{
    clock_t start, finish;
    start = clock();
   
    double duration;
    int i=0,j,m;
    int *data;
    FILE *fp;
   
    if (argc<2) {printf("Not enough inputs,pleas input datafile!\n");exit(1);}

    data = (int *)malloc(MAXDATA*sizeof(int));

    fp = fopen(argv[1],"rb");
    if (fp==NULL) {printf("Error in open %s!\n",argv[1]);exit(1);}

    while(fscanf(fp,"%d",data+i)==1)
        i++;
    qsort ( data,  i,  sizeof ( int ) ,  comp) ;

    printf("[N/2] = %d\n",data[i/2]);
    printf("[N/4] = %d\n",data[3*i/4]);
    printf("[N/8] = %d\n",data[7*i/8]);

    printf("Now printing first 0 to N/8 ranked data!\n");

    m=i/8;

    for(j=0; j<m;j++)
        printf("%dth data = %d\n",j,data[j]);

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;

    printf("Running sort_data spend: %g seconds\n",duration);
}

 时间复杂度n*log(n)

  这是可执行文件,用g++编译

使用方法：cmd下运行: sort_data data.txt

如果要将结果存入文件，运行　sort_data data.txt >outfile.txt

我的电脑的运行时间是0.468s




[ 本帖最后由 mywaylgh 于 2010-3-11 10:36 编辑 ]