对于给定的n个元素数组,找出第k小元素。C语言代码,加注释
时间: 2024-06-03 09:07:04 浏览: 12
#include <stdio.h>
// 交换数组中两个元素的值
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
// 划分函数,用于将数组分为左右两部分,并返回基准元素的下标
int partition(int arr[], int low, int high){
int pivot = arr[high]; // 选择最后一个元素作为基准元素
int i = low - 1; // i 初始化为数组下标 low-1
for(int j=low;j<high;j++){
if(arr[j]<pivot){
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[high]);
return i+1;
}
// 寻找第 k 小元素的函数
int kthSmallest(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 kthSmallest(arr, low, pos-1, k);
}
return kthSmallest(arr, pos+1, high, k-pos+low-1);
}
return -1;
}
int main(){
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3; // 第三小元素
int result = kthSmallest(arr, 0, n-1, k);
printf("第 %d 小元素是 %d", k, result);
return 0;
}
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)