对于给定的 n 个元素的数组a[0:n-1],要求用快速排序法从中找出第 k 小的元素。用c语言写
时间: 2024-06-13 10:04:23 浏览: 127
快速排序法可以用来解决这个问题,具体步骤如下:
1. 选取数组中的一个元素作为基准值(pivot)。
2. 将数组中小于等于基准值的元素放在基准值左边,大于基准值的元素放在基准值右边。
3. 如果基准值左边的元素个数小于k,则在基准值右边的子数组中继续查找第k-(左边元素个数)-1小的元素。
4. 如果基准值左边的元素个数大于等于k,则在基准值左边的子数组中继续查找第k小的元素。
5. 重复以上步骤,直到找到第k小的元素。
下面是用C语言实现的代码:
```
#include <stdio.h>
int partition(int *arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
int quickSelect(int *arr, int left, int right, int k) {
if (left == right) {
return arr[left];
}
int pivotIndex = partition(arr, left, right);
int numLeft = pivotIndex - left + 1;
if (numLeft == k) {
return arr[pivotIndex];
} else if (numLeft > k) {
return quickSelect(arr, left, pivotIndex - 1, k);
} else {
return quickSelect(arr, pivotIndex + 1, right, k - numLeft);
}
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int kthSmallest = quickSelect(arr, 0, n - 1, k);
printf("第%d小的元素是%d", k, kthSmallest);
return 0;
}
```
阅读全文