分治算法对于给定的n个元素的数组a[1..n]，要求从中找出第k小的元素，用c语言解答。

以下是一种基于快速排序思想的分治算法，用于找出数组a中第k小的元素：

#include <stdio.h>

// 交换数组中的两个元素
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 分区函数，返回分区后枢轴元素的位置
int partition(int a[], int left, int right, int pivotIndex)
{
    int pivot = a[pivotIndex];  // 选择枢轴元素
    swap(&a[pivotIndex], &a[right]);  // 将枢轴元素移动到数组最右边
    int storeIndex = left;  // 初始化存储索引

    // 将小于枢轴元素的元素存储在数组左边
    for (int i = left; i < right; i++)
    {
        if (a[i] < pivot)
        {
            swap(&a[i], &a[storeIndex]);
            storeIndex++;
        }
    }

    // 将枢轴元素移动到其正确的位置
    swap(&a[storeIndex], &a[right]);

    return storeIndex;
}

// 找出数组a中第k小的元素，返回其值
int quickSelect(int a[], int left, int right, int k)
{
    if (left == right)  // 数组只有一个元素
    {
        return a[left];
    }

    // 选择一个枢轴元素
    int pivotIndex = left + (right - left) / 2;
    pivotIndex = partition(a, left, right, pivotIndex);

    if (k == pivotIndex)  // 枢轴元素就是第k小的元素
    {
        return a[k];
    }
    else if (k < pivotIndex)  // 第k小的元素在左边
    {
        return quickSelect(a, left, pivotIndex - 1, k);
    }
    else  // 第k小的元素在右边
    {
        return quickSelect(a, pivotIndex + 1, right, k);
    }
}

int main()
{
    int a[] = {16, 7, 3, 20, 17, 8, 9, 19};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;  // 查找第3小的元素

    int kthSmallest = quickSelect(a, 0, n - 1, k - 1);

    printf("The %dth smallest element is %d.\n", k, kthSmallest);

    return 0;
}

在上面的代码中，`partition()`函数用于将数组a分区，并返回枢轴元素的位置。`quickSelect()`函数使用了分治思想，递归地在a的左半边或右半边查找第k小的元素，直到找到为止。

这种算法的时间复杂度为O(n)，与快速排序算法相同，但是不需要完全排序整个数组。