用C++ 写一个 求一个无序数组中第K小的数。 要求在O(N)的时间复杂度内完成，即不对数组进行全员排序。

可以使用快速选择算法来解决这个问题，其时间复杂度为O(N)。

快速选择算法基于快速排序，但不需要完全排序整个数组。它通过每次选择一个基准元素并将数组分为两个部分来工作，然后根据基准元素的位置来确定我们需要搜索的那个部分。

具体地，我们可以首先随机选择一个元素作为基准元素，然后将数组中比该元素小的元素放在它的左边，比该元素大的元素放在它的右边。假设基准元素的位置为p，则左边的子数组中有p个元素小于它，右边的子数组中有n-p-1个元素大于它。如果k=p，则基准元素即为第k小的元素；如果k<p，则我们需要在左边的子数组中继续搜索第k小的元素；如果k>p，则我们需要在右边的子数组中继续搜索第k-p-1小的元素。

下面是使用快速选择算法求解第k小的数的C代码：

#include <stdio.h>
#include <stdlib.h>

int partition(int* nums, int left, int right) {
    int pivot = nums[left];
    int i = left + 1, j = right;
    while (i <= j) {
        while (i <= j && nums[i] < pivot) {
            i++;
        }
        while (i <= j && nums[j] >= pivot) {
            j--;
        }
        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    int temp = nums[left];
    nums[left] = nums[j];
    nums[j] = temp;
    return j;
}

int quickSelect(int* nums, int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }
    int pivotIndex = partition(nums, left, right);
    if (k == pivotIndex) {
        return nums[k];
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}

int findKthSmallest(int* nums, int size, int k) {
    return quickSelect(nums, 0, size - 1, k - 1);
}

int main() {
    int nums[] = {3, 2, 1, 5, 6, 4};
    int size = sizeof(nums) / sizeof(int);
    int k = 2;
    int kthSmallest = findKthSmallest(nums, size, k);
    printf("The %dth smallest element is %d\n", k, kthSmallest);
    return 0;
}

在这个例子中，我们使用数组{3, 2, 1, 5, 6, 4}来演示如何找到第2小的元素。我们首先调用findKthSmallest函数，并将nums数组的大小和k值作为参数传递。在findKthSmallest函数中，我们调用quickSelect函数来实际查找第k小的元素。在quickSelect函数中，我们首先将left和right参数传递给partition函数，以便将数组分为两个部分。然后，我们根据pivotIndex的值决定搜索哪个子数组。如果k等于pivotIndex，则我们找到了第k小的元素；否则，我们递归调用quickSelect函数来搜索左边或右边的子数组。最后，我们在main函数中打印出找到的第k小的元素。