编辑代码

#include <stdio.h>

int partition(int array[], int arrStart, int arrEnd){
    int pivot = array[arrStart];
    int ex = 0;
    int len = arrEnd;

    for(int i = arrStart; i < len; i++){
        if(ex == 0){
            if(array[arrEnd] > pivot){
                array[arrStart] = array[arrEnd];
                arrStart++;
                ex = 1;
            }else{
                arrEnd--;
            }
        }else if(ex == 1){
            if(array[arrStart] < pivot){
                array[arrEnd] = array[arrStart];
                arrEnd--;
                ex = 0;
            }else{
                arrStart++;
            }
        }
    }

    array[arrStart] = pivot;
    return arrStart;
}

int quickSelect(int array[], int arrStart, int arrEnd, int k){
    if(arrStart > arrEnd){
        return -1;
    }

    int pivotOrderPos = partition(array, arrStart, arrEnd);

    if(k == pivotOrderPos){
        return array[k];
    }else if(k < pivotOrderPos){
        quickSelect(array, arrStart, pivotOrderPos - 1, k);
    }else if(k > pivotOrderPos){
        quickSelect(array, pivotOrderPos + 1, arrEnd, k);
    }
}

int main () {
    int array[] = {11, 8, 3, 9, 7, 1, 2, 5};
    int arrStart = 0, arrEnd = sizeof(array) / sizeof(array[0]);
    int k = 3;
    printf("第%d大的元素为%d", k, quickSelect(array, arrStart, arrEnd - 1, k - 1));
    return 0;
}