编辑代码

#include <stdio.h>

void swap(int *arr, int a, int b) {
	int swap = arr[a];
	arr[a] = arr[b];
	arr[b] = swap;
}

int partition(int *arr, int left, int right) {
	int pivot = arr[right];
	int i, j;
	for (i=left-1,j=left; j<right; j++) {
		if (arr[j] >= pivot)
			swap(arr, ++i, j);
	}
	swap(arr, i+1, right);
	
	return i + 1;
}

int findKthValue(int *arr, int left, int right, int k) {
	if (left == right) return arr[left];
	
	int pivotIndex = partition(arr, left, right);
	if (k == pivotIndex) return arr[k];
	else if (k < pivotIndex) return findKthValue(arr, left, pivotIndex-1, k);
	else return findKthValue(arr, pivotIndex+1, right, k);
}

int main() {
	int array0[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 9, 5};
	int arrEnd = sizeof(array0)/sizeof(int);
	int i;
	for (i=0; i<arrEnd; ++i) printf("%d ", array0[i]);
	printf("\n%d\n", findKthValue(array0, 0, arrEnd, 3));

    int array1[] = {};
	arrEnd = sizeof(array1)/sizeof(int);
	for (i=0; i<arrEnd; ++i) printf("%d ", array1[i]);
	printf("\n%d\n", findKthValue(array1, 0, arrEnd, 3));

    int array2[] = {1, 2, 3, 4, 5, 6};
	arrEnd = sizeof(array2)/sizeof(int);
	for (i=0; i<arrEnd; ++i) printf("%d ", array2[i]);
	printf("\n%d\n", findKthValue(array2, 0, arrEnd, 3));

    int array3[] = {6, 5, 4, 3, 2, 1};
	arrEnd = sizeof(array3)/sizeof(int);
	for (i=0; i<arrEnd; ++i) printf("%d ", array3[i]);
	printf("\n%d\n", findKthValue(array3, 0, arrEnd, 3));
	return 0;
}