#include <stdio.h>
int findPivot(int array[], int arrStart, int 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);
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};
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;
}