d153: 六、智力测验

內容 ：
    在Z先生的牧场中，做一头“光明的奶牛”不仅要称体重，还需要考智力。一年一度的智力测验要求极为严格，大约只有一半的奶牛可以通过。则于参加考试的奶牛数量众多，因此如何    划定智力测验“通过线”令Z先生头痛不已，于是他请你解这一难题。
    每只参加测验的奶牛都会得到一个分数（从0到100的整数），将所有的成绩按从高到低的顺序排好后，处在中间位置的分数将会作为“参考分数”提供给Z先生，以便让他决定“通过线”。如果参加测验的奶牛的数目是偶数的话，处于中间的位置的分数将会有两个，此时“参考分数”是其中较小的一个。

輸入說明 ：
    输入第一行是一个整数T（1 <= T <= 100)，表示测试数据的总数。
    每组测试数据的第一行是一个整数N（1 <= n <= 40000），表示参加测验的奶牛的数目。以下的N行依次给出N只奶牛测验的成绩，每行有一个0至100的正整数。

輸出說明 ：
    每组测试数据都输出一个答案，输出“参考分数”。

範例輸入 ：
1
6
97
45
78
62
81
79

範例輸出 ：
78

程式碼 ：

#include <stdio.h>

void swap(int *a, int *b)
{
    int c;
    c = *a;
    *a = *b;
    *b = c;
}

int partition(int arr[], int left, int right) 
{     
    int i, j, s;
    s = arr[right];
    i = left - 1;
     
    for(j = left; j < right; j++)
    {
        if(arr[j] > s)
        {
            i++;
            swap(&arr[i], &arr[j]);           
        }
    }

    swap(&arr[i+1], &arr[right]);
    return i+1;
}

void quicksort(int arr[], int left, int right) 
{     
    int q;     
    
    if(left < right) 
    {         
        q = partition(arr, left, right);         
        quicksort(arr, left, q-1);         
        quicksort(arr, q+1, right);     
    } 
}


int main(void) 
{
    int i, n, times, arr[40000];
    
    scanf("%d",&times);
    while(times--)
    {
        scanf("%d",&n);
        
        for(i=0; i<n; i++)
            scanf("%d",&arr[i]);
            
        quicksort(arr, 0, n-1);
                
        printf("%d\n",arr[n/2]);        
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=d153