C语言实现C++ std::nth_element

C语言中没有直接对应C++中的`std::nth_element`函数，但是可以使用类似的思路来实现。

`std::nth_element`函数是用来寻找序列中第k小（或第k大）的元素。其实现原理是基于快速排序的分治思想。具体来说，它会选择一个基准元素，将序列分为两部分，使得前一部分元素均小于等于基准元素，后一部分元素均大于等于基准元素。如果基准元素的下标刚好是k，则可以直接返回该元素；否则，根据基准元素的下标与k的大小关系，递归地在前半部分或后半部分寻找第k小（或第k大）的元素。

下面是一个用C语言实现的类似`std::nth_element`函数的例子：

#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;
    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;
}

int nth_element(int arr[], int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int pivotIndex = partition(arr, low, high);
        if (pivotIndex == k - 1) {
            return arr[k - 1];
        } else if (pivotIndex > k - 1) {
            high = pivotIndex - 1;
        } else {
            low = pivotIndex + 1;
        }
    }
    return -1; // 如果k非法，返回-1
}

int main() {
    int arr[] = {1, 4, 2, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    int result = nth_element(arr, n, k);
    if (result == -1) {
        printf("k is invalid!\n");
    } else {
        printf("The %d-th smallest element is %d\n", k, result);
    }
    return 0;
}

运行结果为：

The 3-th smallest element is 3

可以看到，该实现与C++中的`std::nth_element`函数类似。