三、(25分)设计分治算法(写出代码)，求解：在一个无序数列中查找第k小的元素，并求解时间复杂度。，请用c语言写代码

以下是基于快速排序的分治算法来查找第k小元素的C语言代码：

#include <stdio.h>

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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

int kthSmallest(int arr[], int low, int high, int k) {
    if (k > 0 && k <= high - low + 1) {
        int pos = partition(arr, low, high);
        if (pos - low == k - 1) {
            return arr[pos];
        } else if (pos - low > k - 1) {
            return kthSmallest(arr, low, pos - 1, k);
        } else {
            return kthSmallest(arr, pos + 1, high, k - pos + low - 1);
        }
    }
    return -1;
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int kth = kthSmallest(arr, 0, n - 1, k);
    printf("%d-th smallest element is %d", k, kth);
    return 0;
}

时间复杂度分析：在快速排序中，每次将一个元素放到它最终的位置上需要O(n)的时间复杂度。在最坏情况下，每次划分都会将数组分成大小为n-1和1的两部分，因此递归树的深度是n，时间复杂度为O(n^2)。但是在平均情况下，每次划分都能将数组分成大小相等的两部分，递归树的深度为log(n)，时间复杂度为O(nlogn)。因此，本算法的时间复杂度在平均情况下为O(nlogn)，在最坏情况下为O(n^2)。