1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4  5 #define N 10000 6  7 int select(int arr[], int n, int k); 8  9 int main(void)10 {11     int * arr;12     int value;13     clock_t elapse;14 15     system("color 0A");16 17     srand((unsigned)time(NULL));18     arr = (int *)malloc(sizeof(int) * N);;19     for (int j = 0; j < N; j++)20     {21         arr[j] = rand() % 100000;22         printf("%d ", arr[j]);23     }24     putchar(‘\n‘);25 26     elapse = clock();27     value = http://www.mamicode.com/select(arr, N, N / 2);28     elapse = clock() - elapse;29     printf("Value: %d, elapsed: %.4lfs\n", value, (double)elapse / 1000);30 31     free(arr);32     system("pause");33     return 0;34 }35  36 /*选择数组中第k个最大者*/37 int select(int arr[], int n, int k)38 {39     int * tmp;40     int i, j, ret;41 42     tmp = (int *)malloc(sizeof(int) * k);43     tmp[0] = arr[0];44     for (i = 1; i < k; i++)            //读入k个元素并降序排列45     {46         tmp[i] = arr[i];47         for (j = i; j > 0; j--)48         {49             if (arr[i] > tmp[j - 1])50             {51                 tmp[j] = tmp[j - 1];52                 tmp[j - 1] = arr[i];53             }54         }55     }56 57     for (i = k; i < n; i++)            //读入arr[k]58     {59         if (tmp[k - 1] < arr[i])60         {61             tmp[k - 1] = arr[i];62             for (j = k - 1; j > 0; j--)63             {64                 if (arr[i] > tmp[j - 1])65                 {66                     tmp[j] = tmp[j - 1];67                     tmp[j - 1] = arr[i];68                 }69             }70         }71     }72 73     ret = tmp[k - 1];74     free(tmp);75     return ret;76 }