问题：求一组数中第k小的元素。 要求：采用分治算法求解以上问题。 1、请用伪码描述该算法。 2、请截图显示实现该算法的c语言代码。 3、当这组数有n个元素时，请写出该算法的运行时间T（n）的递推式，并求时间复杂度O。

1. **伪码描述**：

   Procedure findKthSmallest(arr[], n, k):
       if n == 1:
           return arr[0]
       pivot = partition(arr, n) // 分区操作，将数组分为两部分，一部分小于pivot，另一部分大于等于pivot
       if k == pivot:
           return arr[k]
       elif k < pivot:
           return findKthSmallest(arr, pivot - 1, k)
       else:
           return findKthSmallest(arr[pivot + 1:], n - pivot - 1, k - pivot - 1)
   
   PartitionProcedure(arr[], low, high):
       pivot = arr[high]
       i = low - 1
       for j in range(low, high):
           if arr[j] <= pivot:
               i++
               swap(arr[i], arr[j])
       swap(arr[i+1], arr[high])
       return i + 1

2. **C语言代码实现** (请注意实际的代码会更长，这里仅提供核心部分):

#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 findKthSmallest(int arr[], int n, int k) {
    if (n == 1) return arr[0];

    int pivot_index = partition(arr, 0, n - 1);
    if (k == pivot_index) return arr[k];
    else if (k < pivot_index) return findKthSmallest(arr, pivot_index - 1, k);
    else return findKthSmallest(arr + pivot_index + 1, n - pivot_index - 1, k - pivot_index - 1);
}

3. **运行时间和时间复杂度分析**：
当输入数组有n个元素时，每次分割（partition函数），我们将待查找范围缩小到原来的一半。这是二分查找的思想，所以递归深度为log(n)，对于每一层递归，有一个常数时间的比较和交换操作。因此，总的时间复杂度为 \( O(log(n)) \)。