编辑代码

#include <stdio.h>

// 找基准值在排序前的位置 
int findPivot(int array[], int arrStart, int arrEnd) {
	//return arrStart; //以第一个数为基准
    //return arrEnd; //以最后一个数为基准
    int mid = arrStart + (arrEnd - arrStart)/2;

    if( (array[arrStart]-array[mid])*(array[mid]-array[arrEnd])>0 ) 
        return mid;
    else if((array[mid]-array[arrStart])*(array[arrStart]-array[arrEnd])>0 ) 
        return arrStart;
    else return arrEnd;
}

//返回值就是分区后,基准值所在的位置
//该函数的功能是将比基准值小的数据放在它的左边,比它大的数据放在它的右边
//把基准值放到它排序后的位置
int partition(int array[], int arrStart, int arrEnd, int pivotPos) {
	int arrLen = arrEnd - arrStart;
    if(arrLen < 1 || pivotPos < arrStart || pivotPos > arrEnd) {
        printf("检查你的元素。\n");
        return -1;
    }
    int pivotValue = array[pivotPos];
    array[pivotPos] = array[arrEnd -1];
    int pivotCount = 0;
    int temp;
    for(int i = arrStart; i < arrEnd -1; ++i) {
        if(array[i] > pivotValue) {
            temp = array[arrStart + pivotCount];
            array[arrStart + pivotCount] = array[i];
            array[i] = temp;
            ++pivotCount;
        }
    }
    array[arrEnd - 1] = array[arrStart + pivotCount];
    array[arrStart + pivotCount] = pivotValue;
    //基准值在数组中的位置
    return arrStart + pivotCount;
} 

int findKthValue(int array[], int arrStart, int arrEnd, int k) {
    int arrLen = arrEnd - arrStart;

    if (arrLen < 0 || k < arrStart || k >= arrEnd) {
        printf("检查你的输入!\n");
        return -1;
    }

    if (arrLen == 1 && arrStart == k) return array[arrStart];

    int pivotPos = findPivot(array, arrStart, arrEnd);
    int pivotOrderedPos = partition(array , arrStart, arrEnd, pivotPos);

    //TODO
    if (k == pivotOrderedPos) return array[pivotOrderedPos];

    if (k < pivotOrderedPos) return findKthValue(array, arrStart, pivotOrderedPos, k);
    else return findKthValue(array, pivotOrderedPos+1, arrEnd, k);
}

void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main () {
    printf("\t用例1\n");
    int arr1[] = {11, 8, 3, 9, 7, 1, 2, 5};
    //11 9 8 7 5 3 2 1
    int arrayLen = sizeof(arr1)/sizeof(int);
    int k = 1;
    int result = findKthValue(arr1, 0, arrayLen, k-1);
    printf("The %dth largest element is: %d\n", k, result);
    
	k = 8;
    result = findKthValue(arr1, 0, arrayLen, k-1);
    printf("The %dth largest element is: %d\n", k, result);

    k = -1;
    result = findKthValue(arr1, 0, arrayLen, k-1);
    printf("The %dth largest element is: %d\n", k, result);
    
    return 0;
}