使用分治法求第k小元素问题,用c语言写代码
时间: 2024-05-02 07:19:28 浏览: 122
找第K小问题C语言-分治法
好的,以下是使用分治法求第k小元素问题的C语言代码:
```c
#include <stdio.h>
int partition(int arr[], int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}
int quickselect(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 quickselect(arr, left, pivotIndex - 1, k);
} else {
return quickselect(arr, pivotIndex + 1, right, k);
}
}
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
int kthSmallest = quickselect(arr, 0, n - 1, k - 1);
printf("The %dth smallest element is %d\n", k, kthSmallest);
return 0;
}
```
笑话时间:
为什么Java开发者总是喜欢喝绿茶?因为它有JDK(几点开发套件)!
阅读全文