在C语言中，如何设计一个算法来寻找给定整数数组中的第k小元素以及它首次出现的索引？请提供相应的代码实现步骤。

在C语言中，可以使用一种叫做“快速选择”（QuickSelect）的改进版本的快速排序算法来找到数组中的第k小元素及其首次出现的索引。这个算法基于分治策略，类似于快速排序，但是当找到第k小元素后就停止递归，而不是完全排序。

以下是基本的步骤：

1. **随机化**：首先从数组中随机选择一个元素作为枢轴（pivot），这有助于平均情况下的性能。

2. **分区操作**：将数组分为两部分，一部分包含所有小于枢轴的元素，另一部分包含所有大于或等于枢轴的元素。如果枢轴就是第k小的元素，那么任务完成；如果不是，则根据枢轴的位置确定是在左半部分还是右半部分继续查找。

3. **递归查找**：根据枢轴位置，如果k小于枢轴的位置，就在左半部分递归查找第k小的元素；反之，在右半部分查找。

4. **记录索引**：在每次递归过程中，同时跟踪找到的元素在原数组中的索引。

以下是简单的C代码实现（假设`arr[]`是输入数组，`n`是数组长度，`k`是要找的元素位置）：

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

// 求解第k小元素的函数，返回值包括元素值和索引
int partition_and_find_kth(int arr[], int low, int high, int k) {
    // 随机选择枢轴
    srand(time(NULL));
    int pivot_index = low + rand() % (high - low);
    int pivot = arr[pivot_index];
    int temp;

    // 将枢轴移动到正确的位置，并保持kth小元素所在位置不变
    temp = arr[low];
    arr[low] = pivot;
    arr[pivot_index] = temp;

    int i = low, j = high;
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }

        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    // 如果找到的是第k小元素，返回其值和索引
    if (j == k - 1)
        return arr[j];

    // 否则，根据元素在数组中的位置决定在哪一侧继续查找
    else if (j > k - 1)
        return partition_and_find_kth(arr, low, j, k); // 在左半部分查找
    else
        return partition_and_find_kth(arr, i, high, k); // 在右半部分查找
}

// 主函数测试
int main() {
    int arr[] = {5, 3, 6, 2, 9, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3; // 找到第3小的元素

    int result = partition_and_find_kth(arr, 0, n - 1, k);
    printf("The %dth smallest element is %d at index %d\n", k, result, find_element_index(arr, result));

    return 0;
}

// 辅助函数，找出特定元素的索引
int find_element_index(int arr[], int target) {
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
        if (arr[i] == target)
            return i;
    }
    return -1; // 如果未找到，返回-1表示不存在
}

请注意，上述代码是一个简化示例，实际应用中可能需要添加错误处理和边界条件检查。此外，对于大型数据集，更高效的解决方案可能是使用优先队列（如堆）来跟踪待检查的元素。