C语言快速选择算法：查找第k小的数

a. 问题分析：给定一个长度为n的整数数列和一个整数k，要求找出数列从小到大排序后的第k个数。

b. 解题思路分析：可以使用快速选择算法来解决该问题。快速选择算法是基于快速排序的思想，通过每次选取一个pivot（枢纽元素）将数列划分为两部分，一部分小于pivot，一部分大于pivot。然后根据pivot的位置和k的关系，决定继续在pivot的左边或右边进行划分，直到找到第k个数。

c. 完整的代码注释如下：

#include <stdio.h>

// 快速选择算法
int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) {  // 数列中只有一个数
        return arr[left];
    }
    
    // 选取pivot
    int pivot = arr[left];
    int i = left, j = right;
    
    // 进行划分
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    
    // pivot的位置为i
    arr[i] = pivot;
    
    // 判断pivot的位置和k的关系
    if (i - left + 1 == k) {  // 第k个数为pivot
        return pivot;
    } else if (i - left + 1 < k) {  // 第k个数在pivot的右边
        return quickSelect(arr, i + 1, right, k - (i - left + 1));
    } else {  // 第k个数在pivot的左边
        return quickSelect(arr, left, i - 1, k);
    }
}

int main() {
    int arr[] = {2, 1, 3, 6, 4, 5, 0, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    
    int result = quickSelect(arr, 0, n - 1, k);
    printf('第%d小的数为：%d\n', k, result);
    
    return 0;
}

运行结果：

第3小的数为：2