Contents

1. 1. 分析：

输入n个整数和一个正整数k(1<=k<=n)，输出这些整数从小到大排序后的第k个。注意n<=10^7

分析：

　　用快速排序的特点，会选出一个中值然后把小于他的放在左边，大于他的放在右边，最后比较k和中值序号来选择接下来是去左边找还是右边

#include <cstdio>
#include <cstdlib>

int k, n;
int arr[1000];

void qsort(int a[], int left, int right){

    if(left > right)//error
        return ;

    int i = left, j = right, key = a[left];
    while(i < j)
    {
        while(i < j && a[j] >= key)
            j--;
        if(i < j)
            a[i++] = a[j];
        while(i < j && a[i] < key)
            i++;
        if(i < j)
            a[j--] = a[i];
    }
    a[i] = key;
    if(k == i){
        printf("result: %d\n", arr[i]);//输出第k大数
        return ;
    }
    else if(k < i){
        qsort(a, left, i);
    }else if(k > i){
        qsort(a, i + 1, right);
    }
}

void solve(){

    while(1){
        scanf("%d", &k);
        qsort(arr, 1, n);
    }
}

int main(){

    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d", &arr[i]);
        }
        solve();
    }
    return 0;
}