在一个数组中选择第k小元素的C语言代码
时间: 2024-05-27 08:12:37 浏览: 16
以下是快速选择算法的 C 语言代码,用于在无序数组中选择第 k 小的元素:
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 pos = partition(arr, low, high);
if (pos - low == k - 1)
return arr[pos];
if (pos - low > k - 1)
return quickselect(arr, low, pos - 1, k);
return quickselect(arr, pos + 1, high, k - pos + low - 1);
}
return -1;
}
int main() {
int arr[] = {5, 3, 8, 6, 7, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
printf("k-th smallest element is %d", quickselect(arr, 0, n-1, k));
return 0;
}
注意:这仅仅是一个示例,并没有在代码中实现对输入值的检查。实际
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)