Как в массиве найти некое количество наибольший или наименьших значений

Вы можете определить функцию, которая будет находить любое количество максимальных элементов в целочисленном массиве. Для этого просто нужно передавать в функцию массив нужной размерности для хранения максимальных значений.

Функция возвращает число максимальных элементов, так как в общем случае вы можете запросить найти больше максимальных элементов, чем общее количество элементов имеется в массиве, или, например, когда вам передается пустой массив.

Ниже приведена демонстрационная программа

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
size_t max_elements(const int *a, size_t n, int *max, size_t m)
{
    size_t k = 0;
    for (size_t i = 0; i < n; i++)
    {
        size_t j = 0;
        while (j < k && !(a[i] > max[j])) j++;
        if (j == k )
        {
            if ( k < m ) max[k++] = a[i];
        }
        else
        {
            memmove(max + j + 1, max + j, 
                    ( k < m ? k - j: k - j - 1 ) * sizeof(int));
            max[j] = a[i];
            if (k < m) ++k;
        }
    }
    return k;
}
#define N1  10
#define M   3
int main()
{
    int a[N1];
    int max[M];
    srand((unsigned int)time(NULL));
    for (size_t i = 0; i < N1; i++) a[i] = rand() % (2 * N1);
    for (size_t i = 0; i < N1; i++) printf("%d ", a[i]);
    printf("\n");
    size_t k = max_elements(a, N1, max, M);
    if (k != 0)
    {
        printf("%zu max elements are ", k);
        for (size_t i = 0; i < k; i++) printf("%d ", max[i]);
        printf("\n");
    }
}

Ее вывод на консоль может выглядеть следующим образом:

13 17 8 9 14 10 2 15 3 19
3 max elements are 19 17 15

Аналогичным образом вы можете найти минимальные элементы. Все, что вам для этого требуется это изменить условие в этом цикле

while (j < k && !(a[i] > max[j])) j++;
                ^^^^^^^^^^^^^^^^  

Как вариант -

void max3(int * a, int N)
{
    int i, retry;
    for(i = 0; i < N-3; ++i)
    {
        for(retry = 1; retry;)
        {
            retry = 0;
            for(int j = N-1; j >= N-3; --j)
            {
                if (a[i] > a[j])
                {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                    retry = 1;
                    break;
                }
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    int a[] = { 3, 5, 7, 1, 9, 2, 8, 0, 1, 9 };
    max3(a,sizeof(a)/sizeof(a[0]));
    for(int j = sizeof(a)/sizeof(a[0])-3; j < sizeof(a)/sizeof(a[0]); ++j)
    {
        printf("%3d",a[j]);
    }
    printf("\n");
}

Про эффективность - ну, O(n), потому как 3 - константа :)