快速选择算法 题目描述：快速选择算法是一种在未排序的列表中查找第k小（或第k大）元素的高效算法。它是快速排序算法的变种，但不需要对整个数组进行完全排序，平均时间复杂度为O(n)，最坏情况下为O(n²)。 解题过程： 算法思想 快速选择基于快速排序的分区思想。在快速排序中，我们选择一个基准元素将数组分为两部分：左边部分的所有元素小于等于基准，右边部分的所有元素大于基准。快速选择利用这个特性，只在包含目标元素的那部分继续查找，从而避免了对整个数组的排序。 算法步骤 选择一个基准元素（pivot） 对数组进行分区，将小于基准的元素放在左边，大于基准的元素放在右边 比较基准元素的最终位置与k的关系： 如果基准位置正好是k，则返回基准元素 如果基准位置大于k，则在左半部分递归查找第k小元素 如果基准位置小于k，则在右半部分递归查找第(k - 基准位置 - 1)小元素 详细实现过程 让我们通过具体例子来理解：在数组[ 3, 2, 1, 5, 4 ]中查找第3小的元素。 步骤1：选择基准 通常选择最后一个元素作为基准，这里选择4作为基准。 步骤2：分区操作 设置两个指针：i指向小于基准的区域末尾，j遍历数组 初始状态：[ 3, 2, 1, 5, 4 ]，i = -1, j = 0 j=0：3<4，i++=0，交换arr[ 0]和arr[ 0 ] → 数组不变 j=1：2<4，i++=1，交换arr[ 1]和arr[ 1 ] → 数组不变 j=2：1<4，i++=2，交换arr[ 2]和arr[ 2 ] → 数组不变 j=3：5>4，不交换 最后交换arr[ i+1]和pivot → 交换arr[ 3]和arr[ 4 ] 分区结果：[ 3, 2, 1, 4, 5 ]，基准4的位置是3 步骤3：判断递归方向 我们要找第3小的元素（k=2，因为通常从0开始计数） 基准位置3 > 2，所以在左半部分[ 3, 2, 1 ]中继续查找第2小的元素 步骤4：递归左半部分 在[ 3, 2, 1 ]中查找第2小的元素，选择1作为基准 分区过程： 初始：[ 3, 2, 1 ]，i = -1, j = 0 j=0：3>1，不交换 j=1：2>1，不交换 交换arr[ i+1]和pivot → 交换arr[ 0]和arr[ 2 ] 分区结果：[ 1, 2, 3 ]，基准1的位置是0 步骤5：继续判断 目标位置2 > 基准位置0，所以在右半部分[ 2, 3 ]中查找第(2-0-1)=1小的元素 步骤6：在[ 2, 3 ]中查找第1小的元素 选择3作为基准，分区后得到[ 2, 3 ]，基准位置是1 目标位置1 = 基准位置1，找到结果：3 时间复杂度分析 最好情况：每次分区都能将数组平分，时间复杂度为O(n) 平均情况：O(n) 最坏情况：每次选择最差基准，时间复杂度为O(n²) 优化策略 为了避免最坏情况，可以采用随机选择基准或三数取中等策略来提高算法性能。