n个最大数问题

时间：2010-10-28 来源：gavinx

从一堆数里找出n个最大数的程序实现。时间复杂度为O(n)

#include <stdio.h>
#define NUM 6
int a[] = {1,3,4,5,20, 1, 3, 7, 73, 28, 185, 102, 3, 4, 6, 9, 200, 23, 156, 67, 89, 98, 105};
int b[NUM];
main()
{
    int i, j, k;

    /* need to sort the 1st 5 line */
    for ( i = 0; i < NUM; i++)
    {
        b[i] = i+1;
    }
    printf("num=%d\n", sizeof(a)/sizeof(int));
    for (i=0; i < (sizeof(a)/sizeof(int)); i++)
    {
        if (a[i] <= b[0])
            continue;
        else
        {
            int flag = 0;
            for (j = 0; j < NUM && !flag; j++)
                if (a[i] < b[j]) break;
                else
                    if (a[i]==b[j]) flag = 1;
            if (!flag)
            {
                for (k = 0; k < j-1; k++)
                    b[k] = b[k+1];
                b[j-1] = a[i];
            }
        }
    }
    for (j = 0; j < NUM; j++) printf(" %d", b[j]);
}