输入：数组A，查找范围[left, right]，目标排名k
划分阶段：
选择A[left]作为基准元素pivot
对A[left...right]进行划分，使得：
左边所有元素 ≤ pivot
右边所有元素 ≥ pivot
返回基准元素的最终位置pos
计算排名：
计算基准元素在当前子数组中的排名：currentRank = pos - left + 1
分治决策：
情况1：如果currentRank = k
基准元素就是第k小的元素，返回A[pos]
情况2：如果currentRank > k
第k小的元素在左半部分
在A[left...pos-1]中递归查找第k小的元素
情况3：如果currentRank < k
第k小的元素在右半部分
在A[pos+1...right]中递归查找第(k - currentRank)小的元素
最好情况时间复杂度：O(n)
发生条件：
每次划分都能将数组均匀分成两半
或者第一次划分就找到了第k小的元素
最坏情况时间复杂度：O(n²)
发生条件：
每次划分都极度不平衡
例如：数组已排序且总是选择最小/最大元素作为基准
或者第k个元素总是在最大的那个分区中
体会和思考：分治法将复杂问题划分成多个子问题，将复杂问题简单化，针对子问题可以专门优化
好文要顶 关注我 收藏该文 微信分享