编辑代码

#include <stdio.h>  
  
// 定义了一个交换函数，用于交换两个整数的值。函数接受两个整数的指针作为参数。  
void swap(int* a, int* b) {    
    // 声明一个临时变量t并把a指针所指向的值赋给它  
    int t = *a;    
    // 把b指针所指向的值赋给a指针所指向的值  
    *a = *b;    
    // 把t的值（也就是原来a的值）赋给b指针所指向的值  
    *b = t;    
}   
  
// 定义了一个函数用于对数组进行分割。该函数选择数组的最后一个元素作为主元（pivot）。  
// 函数接受一个整数数组、一个low索引和一个high索引作为参数。  
int partition(int arr[], int low, int high) {    
    // 主元的选择：取数组的最后一个元素作为主元  
    int pivot = arr[high];    
    // 初始化一个变量i为low-1，这将是小于主元的元素的起始索引  
    int i = (low - 1);    
  
    // 遍历从low到high-1的数组元素  
    for (int j = low; j <= high - 1; j++) {    
        // 如果当前元素小于主元，则把i增加1，并把i所指向的元素和j所指向的元素交换  
        if (arr[j] < pivot) {    
            i++;    
            swap(&arr[i], &arr[j]);    
        }    
    }  
    // 把主元放在i+1的位置，这是小于主元的元素的结束位置  
    swap(&arr[i + 1], &arr[high]);    
    // 返回小于主元的元素的结束位置，这个位置的元素就是第k大的元素（如果存在第k大的元素的话）  
    return (i + 1);    
}  
  
// 定义了一个函数用于快速选择第k大的元素。函数接受一个整数数组、一个low索引和一个high索引作为参数。  
int quickSelect(int arr[], int low, int high, int k) {    
    // 如果low和high相等，说明数组中只有一个元素，直接返回该元素  
    if (low == high) {    
        return arr[low];    
    }    
  
    // 选择主元并把数组分为两部分：小于主元的元素和大于主元的元素  
    int pi = partition(arr, low, high);    
  
    // 如果主元的位置等于k-1，那么主元就是我们要找的元素，直接返回主元  
    if (pi == k - 1) {    
        return arr[pi];    
    // 如果主元的位置小于k-1，那么主元左边的元素都小于我们要找的元素，可以在右边部分继续查找  
    } else if (pi < k - 1) {    
        return quickSelect(arr, pi + 1, high, k);    
    // 如果主元的位置大于k-1，那么主元右边的元素都大于我们要找的元素，可以在左边部分继续查找  
    } else {    
        return quickSelect(arr, low, pi - 1, k);    
    }    
}  
     
int main() {    
    int arr[] = {11,8,3,9,7,1,2,5};  
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组的长度，两者相除就是数组的长度。  
    int k = 4;  
    
    // 调用quickSelect函数查找第k大的元素并把结果存储在result变量中。
  // 这里调用的quickSelect函数是针对整个数组进行查找的。数组的起始索引0和结束索引n-1
    int result = quickSelect(arr, 0, n - 1, k);  
    printf("第%d大的元素是：%d\n", k, result);  
  
    return 0;  
}