编辑代码

#include <stdio.h>
#include <stdbool.h>

// 返回基准值在数组中的位置
int findPivotPos(int array[], int arrStart, int arrEnd) {
    return arrStart;
}

// 根据基准值进行分区，把比基准值大的元素放右边，小的元素放左边
// 返回值：基准值在排序后的位置
int partition(int array[], int arrStart, int arrEnd, int pivosPos) {
    int pivosValue = array[pivosPos];
    array[pivosPos] = array[arrEnd - 1];

    int ItPivosValueCount = 0;
    for (int i = arrStart; i < arrEnd - 1; i++) {
        if (array[i] < pivosValue) {
            int temp = array[arrStart + ItPivosValueCount];
            array[arrStart + ItPivosValueCount] = array[i];
            array[i] = temp;
            ++ItPivosValueCount;
        }
    }
    array[arrEnd - 1] = array[arrStart + ItPivosValueCount];
    array[arrStart + ItPivosValueCount] = pivosValue;

    return arrStart + ItPivosValueCount;
}

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

    if(arrEnd < 0 || k < arrStart || k >= arrEnd) {
        return false;
    }

    if(arrLen == 1 && arrStart == k) {
        return true;
    }

    int pivosPos = findPivotPos(array, arrStart, arrEnd);

    int pivotOrderedPos = partition(array, arrStart, arrEnd, pivosPos);

    if(k == pivotOrderedPos) {
        return true;
    }

    bool ret = false;

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

    return ret;
}

int main() {
    int array[] = {11, 8, 3, 9, 7, 1, 2, 5};
    bool c = findKthValue(array, 0, 8, 1);
    printf("%d ", c);
    return 0;
}