函数预览

int finding(int l,int r,int k){
	if(l==r) return a[l];
	int i=l,j=r;
	int mid=(l+r)/2;
	int x=a[mid];
	while(i<=j){
		while(a[i]<x) i++;
		while(a[j]>x) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++;
			j--;
		}
	}
	if(k<=j) return finding(l,j,k);
	else if(i<=k) return finding(i,r,k);
	else return a[k];
}

代码拆解分析

1.递归终止条件

if(l == r) return a[l];

如果左边界l和右边界r相等，那么就说明现在的区间只有一个元素了，那么不管如何，这个元素就一定是我要找的答案了，已经不需要再去做什么了，就可以直接返回了

2.选择基准值-中间元素

int mid = (l + r) / 2;  // 计算中间位置
int x = a[mid];         // 选中间元素作为基准值

这个就是去选择一个元素作为基准，那就选择中间元素，有一点二分的思想在这里。

3.进行分区操作

int i = l, j = r;  // i从左往右走，j从右往左走
while(i <= j) {
    while(a[i] < x) i++;  // 左指针找“不小于基准”的数
    while(a[j] > x) j--;  // 右指针找“不大于基准”的数
    if(i <= j) {          // 如果i还在j左边，交换这两个数
        swap(a[i], a[j]);
        i++;  // 交换后i右移，j左移
        j--;
    }
}

这个就是一种双指针的思想，我的目标是达到排序功能，那么我就让基准值左边的元素都小于等于基准值，右边元素都大于等于基准值，有一点双指针的思想，用两个指针 i 和 j 分别从左右两端向中间移动，把不符合条件的元素交换位置。i是从左往右的，j是从右往左的，while语句干啥的呢？就是i是左边界，j是有边界对不对，那么我就让左边界往右走，右边界往左走，直到左边界大于右边了，哎，那他俩是不是越界了，那不就得停了吗？所以我就达到了遍历的作用。

举个例子：

假设数组是 [5, 3, 8, 4, 2, 7, 1, 6]，基准值 x 选中间元素 a[3]=4。

int i = l, j = r;  // 初始时，i指向左边界l=0，j指向右边界r=7

左指针 i 向右移动

while(a[i] < x) i++;  // 只要当前元素小于基准值，就继续右移

a[0]=5 ≥4 → i 停在位置 0

右指针向左移动

while(a[j] > x) j--;  // 只要当前元素大于基准值，就继续左移

• a[7]=6 >4 → j 左移到 7
• a[6]=1 <4 → j 停在位置 6。

交换i和j位置的元素（因为他们不该待在不属于他们的位置）

if(i <= j) {          // 此时i=0 ≤ j=6，满足条件
    swap(a[i], a[j]);  // 交换a[0]=5和a[6]=1
    i++;  // i右移到1
    j--;  // j左移到5
}

交换后数组变成：[1, 3, 8, 4, 2, 7, 5, 6]，此时 i=1，j=5。证明我已经把1前的，5后的数字都放在了他们该待的一边（就是左边的比中间那个数小，右边的比中间那个数大）

继续移动指针，重复交换

• 左指针 i 继续右移：a[1]=3 <4 → i 右移到 2，a[2]=8 ≥4 → 停在位置 2。
• 右指针 j 继续左移：a[5]=7 >4 → j 左移到 4，a[4]=2 <4 → 停在位置 4。
• 交换 i=2 和 j=4 的元素：a[2]=8 和 a[4]=2 交换，数组变为 [1, 3, 2, 4, 8, 7, 5, 6]，然后 i=3，j=3

指针相遇，结束循环

• 左指针 i 右移：a[3]=4 ≥4 → 停在位置 3。
• 右指针 j 左移：a[3]=4 ≤4 → 停在位置 3。
• 交换 i=3 和 j=3 的元素（自己和自己交换，无变化），然后 i=4，j=2。
• 此时 i > j，外层循环结束。

最终分区结果

• 左半部分 [1, 3, 2]：所有元素 ≤4
• 右半部分 [8, 7, 5, 6]：所有元素 ≥4
• 基准值 4 被放到了正确的位置（索引 3）。

再来一个完整的例子：

假设数组为 [5, 3, 8, 4, 2]，基准值 x = 4（中间元素），初始 l=0, r=4。

1. 初始状态

i=0          j=4
↓            ↓
[5, 3, 8, 4, 2]  基准值x=4

2. 移动指针 i 和 j

• i 向右移动：a[0]=5 ≥4 → 停在 i=0
• j 向左移动：a[4]=2 ≤4 → 停在 j=4

3. 交换元素

交换后数组变为 [2, 3, 8, 4, 5]，指针位置更新为：

  i=1      j=3
  ↓        ↓
[2, 3, 8, 4, 5]

4. 继续移动指针

• i 向右移动：a[1]=3 <4 → i=2；a[2]=8 ≥4 → 停在 i=2
• j 向左移动：a[3]=4 ≤4 → 停在 j=3

5. 再次交换元素

交换后数组变为 [2, 3, 4, 8, 5]，指针位置更新为：

      j=2 i=3
      ↓   ↓
[2, 3, 4, 8, 5]

此时 i=3 > j=2，外层循环结束。

最终分区结果

• 左半部分（索引 [l, j]）：[2, 3]（所有元素 ≤4）
• 基准值（位置 j+1）：a[3]=4
• 右半部分（索引 [i, r]）：[8, 5]（所有元素 ≥4）

好的如果到这里你都看懂了，那么差不多快速排序你也就懂得差不多了，如果前面的逻辑没有理清楚，那么建议先把前面的理清楚再继续看。

好的，那么我们分区的意义是什么吗？他会对我找到这个第K个小的元素有什么作用呢，我来回答这个问题，分区之后我们的基准值的左边都小于等于他了，基准值右边都大于等于他了，那么我们这两个区里面的元素的相对大小其实是没有意义的，我们只需要去根据k和基准值的相对位置关系去确定第 k 小的数在左半部分还是右半部分，从而只递归处理一半的数组，这样就节省了时间。

举个例子：

假设数组是 [5, 3, 8, 4, 2, 7, 1, 6]，我们要找第 4 小的元素（k=3，索引从 0 开始）。

分区后：数组可能变成 [1, 3, 2, 4, 8, 7, 5, 6]（基准值 4 在正确位置）。

• 基准值 4 的索引是 3，恰好等于 k=3 → 直接返回 4，结束算法。
• 此时数组整体并未排序，但我们已经找到了目标元素

4.递归实现

那你就要问了，那我如果找的k=4呢，k=2呢，那么就是接下来的递归语句了：

if(k<=j) return finding(l,j,k);
	else if(i<=k) return finding(i,r,k);
	else return a[k];

那么首先看if里的条件：

这个实现的功能就是根据分区结果，判断第 k 小的元素在哪里

在分区操作后，数组被分成三部分：

1. 左半部分（索引 [l, j]）：所有元素 ≤ 基准值
2. 基准值（索引 j+1 或 i-1）
3. 右半部分（索引 [i, r]）：所有元素 ≥ 基准值

分三种情况讨论

1. 情况 1：k ≤ j（k 在左半部分）

if(k <= j) return finding(l, j, k);

解释：
如果 k ≤ j，说明第 k 小的元素位于左半部分（索引范围 [l, j]）。
示例：
假设分区后数组为 [2, 3, 4, 8, 5]，基准值 4 在位置 2，j=1，i=3。
如果要找第 1 小的元素（k=1），因为 k=1 ≤ j=1，递归处理左半部分 [2, 3]。

2. 情况 2：k ≥ i（k 在右半部分）

else if(i <= k) return finding(i, r, k);

解释：
如果 k ≥ i，说明第 k 小的元素位于右半部分（索引范围 [i, r]）。
示例：
继续上面的数组，若要找第 3 小的元素（k=3），因为 k=3 ≥ i=3，递归处理右半部分 [8, 5]。

3. 情况 3：k 在基准值位置

else return a[k];

解释：
如果 k 既不在左半部分，也不在右半部分，说明 k 恰好是基准值的位置（即 k = j+1 = i-1），直接返回 a[k]。
示例：
若要找第 2 小的元素（k=2），恰好等于基准值 4 的位置，直接返回 a[2]=4。

那么经过递归处理就总会到最后k恰好在你的基准位置了，就可以了。

来一个完整的流程，体会一下：

我们以数组 [5, 3, 8, 4, 2] 为例，查找第 3 小的元素（k=3，索引从 1 开始）

初始状态

数组: [5, 3, 8, 4, 2]
目标: 第3小的元素 (k=3)
初始左右边界: l=0, r=4

步骤 1：选择基准值

选择中间元素 a[mid] 作为基准值：

mid = (l + r) / 2 = (0 + 4) / 2 = 2
基准值 pivot = a[2] = 8

步骤 2：分区过程

使用双指针 i 和 j 进行分区：

初始指针位置: i=0, j=4

[5, 3, 8, 4, 2]
 ↑           ↑
 i           j

1. 移动指针 i

• i 从左向右移动，寻找第一个 ≥ 基准值 8 的元素：

a[0]=5 <8 → i右移
a[1]=3 <8 → i右移
a[2]=8 ≥8 → i停在位置2

2. 移动指针 j

• j 从右向左移动，寻找第一个 ≤ 基准值 8 的元素：

a[4]=2 ≤8 → j停在位置4

3. 交换 i 和 j 位置的元素

• 此时 i=2 ≤ j=4，交换 a[2] 和 a[4]：

交换前: [5, 3, 8, 4, 2]
交换后: [5, 3, 2, 4, 8]

• 移动指针：i++ → i=3, j-- → j=3

4. 继续移动指针

• i=3: a[3]=4 <8 → i右移 → i=4
• j=3: a[3]=4 ≤8 → j停止

5. 结束条件

• 此时 i=4 > j=3，分区结束。
• 基准值 8 被交换到最终位置 i=4，左侧元素 [5, 3, 2, 4] 均 ≤8，右侧无元素。

步骤 3：判断 k 的位置

• 基准值 8 的索引为 4，对应第 5 小的元素（从 1 开始）。
• 目标 k=3 < 5 → 第 3 小的元素在左半部分 [5, 3, 2, 4] 中。

递归处理左半部分

新区间: l=0, r=3
新目标: 第3小的元素 (k=3)

1. 选择基准值

mid = (0 + 3) / 2 = 1
基准值 pivot = a[1] = 3

2. 分区过程

初始指针: i=0, j=3

[5, 3, 2, 4]
 ↑        ↑
 i        j

• 移动 i: a[0]=5 ≥3 → i停在0

• 移动 j: a[3]=4 >3 → j左移 → a[2]=2 ≤3 → j停在2

• 交换 i 和 j:

交换前: [5, 3, 2, 4]
交换后: [2, 3, 5, 4]

• 移动指针：i=1, j=1

• 继续移动:

  • i=1: a[1]=3 ≥3 → i停在1
  • j=1: a[1]=3 ≤3 → j停在1

• 交换 i 和 j（自己和自己交换，无变化），指针移动：i=2, j=0

• 结束条件: i=2 > j=0，分区结束。

• 基准值 3 位于索引 1，左侧 [2] ≤3，右侧 [5, 4] ≥3。

3. 判断 k 的位置

• 基准值 3 的索引为 1，对应第 2 小的元素（从 1 开始）。
• 目标 k=3 > 2 → 第 3 小的元素在右半部分 [5, 4] 中。

递归处理右半部分

新区间: l=2, r=3
新目标: 第1小的元素 (k=1，因为左半部分有2个元素)

1. 选择基准值

mid = (2 + 3) / 2 = 2
基准值 pivot = a[2] = 5

2. 分区过程

初始指针: i=2, j=3

[5, 4]
 ↑  ↑
 i  j

• 移动 i: a[2]=5 ≥5 → i停在2
• 移动 j: a[3]=4 ≤5 → j停在3
• 交换 i 和 j:

交换前: [5, 4]
交换后: [4, 5]

• 移动指针：i=3, j=2
• 结束条件: i=3 > j=2，分区结束。
• 基准值 5 位于索引 3，左侧 [4] ≤5，右侧无元素。

3. 判断 k 的位置

• 基准值 5 的索引为 3，对应第 4 小的元素（从 1 开始）。
• 目标 k=1 < 4 → 第 1 小的元素在左半部分 [4] 中。

最终递归

新区间: l=2, r=2
新目标: 第1小的元素 (k=1)

• 区间只剩一个元素 a[2]=4，直接返回。

OVER!