#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;
}