选择问题 对于给定的n个元素数组,找出第k小元素,c语言实现
时间: 2023-05-22 14:04:08 浏览: 66
这可以通过使用快速选择算法来解决,该算法与快速排序类似,但是只需要对第k小元素所在的部分进行排序。以下是使用C语言实现的示例代码:
#include <stdio.h>
#include <stdlib.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
int quickSelect(int arr[], int low, int high, int k) {
if (k > 0 && k <= high - low + 1) {
int pi = partition(arr, low, high);
if (pi - low == k - 1) {
return arr[pi];
} else if (pi - low > k - 1) {
return quickSelect(arr, low, pi - 1, k);
} else {
return quickSelect(arr, pi + 1, high, k - pi + low - 1);
}
}
return -1;
}
int main() {
int arr[] = {10, 4, 5, 8, 6, 11, 26};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3; // 求第3小元素
int kthSmallest = quickSelect(arr, 0, n - 1, k);
printf("%d", kthSmallest); // 输出第3小元素的值:6
return 0;
}
注意:在实际应用中,还需要注意一些边界条件和输入的合法性检查。