给我一个分治法求解输入 n 个数字，然后输出第 k 小的数，最小的数是第 0 小

可以使用快速选择算法（QuickSelect），是基于快速排序算法的一种变形。

算法步骤如下：

1. 选取一个 pivot 元素，将数组分为两部分：小于 pivot 的元素和大于等于 pivot 的元素。

2. 判断 pivot 元素在第几个位置，如果该位置为 k，则直接返回 pivot；如果该位置小于 k，则在大于等于 pivot 的部分继续寻找第 k 小的元素；如果该位置大于 k，则在小于 pivot 的部分继续寻找第 k 小的元素。

3. 重复步骤 1 和 2，直到找到第 k 小的元素。

代码实现如下：

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 quickSelect(int arr[], int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }
    int pivotIndex = partition(arr, low, high);
    if (pivotIndex == k) {
        return arr[pivotIndex];
    } else if (pivotIndex < k) {
        return quickSelect(arr, pivotIndex+1, high, k);
    } else {
        return quickSelect(arr, low, pivotIndex-1, k);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << quickSelect(arr, 0, n-1, k) << endl;
    return 0;
}