找出数组中第 k 个小的元素C语言
时间: 2023-05-30 10:05:10 浏览: 140
可以使用快速选择算法来找出数组中第 k 小的元素。
以下是示例代码:
```c
#include <stdio.h>
int partition(int* arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; 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[right];
arr[right] = temp;
return i + 1;
}
int quickSelect(int* arr, int left, int right, int k) {
if (left == right) {
return arr[left];
}
int pivotIdx = partition(arr, left, right);
int numSmaller = pivotIdx - left + 1;
if (numSmaller == k) {
return arr[pivotIdx];
} else if (numSmaller > k) {
return quickSelect(arr, left, pivotIdx - 1, k);
} else {
return quickSelect(arr, pivotIdx + 1, right, k - numSmaller);
}
}
int main() {
int arr[] = {5, 7, 2, 8, 4, 6, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int kthSmallest = quickSelect(arr, 0, n - 1, k);
printf("The %dth smallest element is %d\n", k, kthSmallest);
return 0;
}
```
在上面的代码中,`partition()` 函数实现了快速排序中的分区操作,将数组分成两部分,左边的元素都小于等于枢轴元素,右边的元素都大于枢轴元素。
`quickSelect()` 函数则使用快速选择算法来找出数组中第 k 小的元素。它首先通过调用 `partition()` 函数将数组分成两部分,然后计算出左半部分的元素个数 `numSmaller`。如果 `numSmaller` 等于 k,那么枢轴元素就是第 k 小的元素。如果 `numSmaller` 大于 k,那么第 k 小的元素一定在左半部分,递归调用 `quickSelect()` 函数来处理左半部分。如果 `numSmaller` 小于 k,那么第 k 小的元素一定在右半部分,递归调用 `quickSelect()` 函数来处理右半部分,同时需要将 k 减去左半部分的元素个数。
在上面的示例中,数组 `{5, 7, 2, 8, 4, 6, 3}` 中第 3 小的元素是 4。