用分治法从n个数中查找第k个小元素 。c语言代码

以下是使用分治法查找第k个小元素的C语言代码：

#include <stdio.h>

// 交换两个元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// 分割数组并返回分割点
int partition(int arr[], int left, int right) {
int pivot = arr[right]; // 选择最后一个元素为基准值
int i = left - 1; // i为分割点
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[right]);
return i+1;
}

// 查找第k个小元素
int kthSmallest(int arr[], int left, int right, int k) {
if (k > 0 && k <= right - left + 1) {
int pos = partition(arr, left, right); // 分割点
if (pos - left == k - 1) {
return arr[pos];
}
if (pos - left > k - 1) {
return kthSmallest(arr, left, pos-1, k);
}
return kthSmallest(arr, pos+1, right, k-pos+left-1);
}
return -1;
}

int main() {
int arr[] = {3, 7, 2, 5, 1, 4, 6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
int kth = kthSmallest(arr, 0, n-1, k);
printf("第%d个小元素是：%d", k, kth);
return 0;
}