贴一个c++版

#include <iostream>
#include <vector>

using namespace std;
vector<int> a;


int quick_sort(int l, int r, int k) {
    if(l >= r) return a[k];

    int x = a[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    if (k <= j) return quick_sort(l, j, k);
    else return quick_sort(j + 1, r, k);
}

int main() {
    int n, k;
    cin >> n >> k;
    a = vector<int>(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << quick_sort(0, n - 1, k - 1) << endl;

    return 0;
}

quick_sort里的return右边的时候，k是不是要改变呀

哦不用不用，前面if里的条件看错了

为什么不能 k==j的时候直接返回

为什么洛谷的第k小整数用模板只能ac一个数据，我看题目差不多啊

我也想知道

洛谷那题里相同大小的整数只算一次，和这题不一样。按照数据规模，可以在输入时去掉重复数字。

对的，我最后发现了，感谢感谢

什么意思啊

洛谷也不是啊，洛谷也没去重

如果k==j时，只能说明第k个数在j的左边（包括j），但左边如果不知一个数，他们不一定时有序的因为他是先i++do while，而不是while，j–，最后在交换（因为这样第j=k个数一定是第k大的，因为这种情况下，最后一次会与哨兵交换）

这个思路也不错~

没想到空降大佬，受宠若惊，哈哈

do-while循环为什么不判断i是否越界呢？如果第一个数字是当前最大的数，第一轮while下标不就越界了吗？

你忽略了等于的情况吧，等于的话也是不会往后走的

y 总好像采纳了 这个 方法，我看 视频 已经 是这个方法了。

y总视频时间戳是8月19，而且明显两方法不同

k-1，好思路

简单修改y总模版为这个思路

#include <iostream>

using namespace std;
const int N = 100000 +10;
int q[N];

int   quick_sort(int q[],int l,int r,int k){
    if(l>=r) return q[l];
    int i=l-1,j=r+1,x=q[(r+l)>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j){
            swap(q[i],q[j]);
        }
    }

    // if(j-l+1>=k){
    //     return quick_sort(q,l,j,k);
    // }
    // else return quick_sort(q,j+1,r,k-(j-l+1));
    if(k<=j)return quick_sort(q,l,j,k);//继续找下标为k的数
    else return quick_sort(q,j+1,r,k);


}
int main(){
    int n,k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &q[i]);
    }
    cout<<quick_sort(q,0,n-1,k-1);//目的是找到下表为k-1的数


    return 0;
}

全网最清晰代码
https://www.acwing.com/solution/content/138598/

n+n/2+n/4+n/8+....~=2n

else return quickSort(j+1, r, k);
这里递归右半边界的时候比较与y总的模板为什么不用减去前半边界的个数啊。进入else不是已经说明第k个数右半边界么。第k个数不是相对于整个数组的么。没看懂，求教

你好，这个你弄明白了吗？

因为这个方法比较的是下标的位置，第k个数是有序之后下标为k-1的数，j是左边跟右边的分界点的下标

思路很不错哦，不过scanner挺容易超时的吧，数据大的时候

把它引入我的题解，嘿嘿，%%%

这样的超时怎么解决啊

试试bufferreader

BufferedReader即可。

其实y总每次写的代码虽然不是最简单的，但却是最有用的，我学了很久感触挺深的。这个函数可以求在一个数组中任意区间【l, r】的第k小的数，这个挺通用的

为什么最后递归右半边界的时候还是传递的k，不是应该减去前半边界限的个数吗

您好，想问一下，为什么‘if(l >= r) return A[k];’这里返回的是A[K]?如果一开始就是l>=r?

#include [HTML_REMOVED]
using namespace std;

const int N = 1e6 + 10;

int n,k;
int q[N];

void quick_sort(int q[], int l, int r) {
if (l >= r) return;
int x = q[l];
int i = l - 1;//在左右两侧，是因为不可以直接指向i和j，否则下面的dowhile循环没办法判断第一个是否属于swap交换的范围
int j = r + 1;//其实这里是用双指针思想，利用两个不同的指针指向两个不同的位置，分别进行前进，观察好–和的位置
while (i < j) {
do i ; while (q[i] < x);
do j – ; while (q[j] > x);
if (i < j) swap(q[i],q[j]);
}
quick_sort(q, l, j);//利用递归思想处理杂乱的两方数组
quick_sort(q, j + 1, r);
}

int main () {
scanf(“%d %d”, &n,&k);
for (int i = 0; i < n; i++) {
scanf(“%d”, &q[i]);
}
quick_sort(q, 0, n - 1);
printf(“%d”,q[k-1]);

}
贴一个c++版本

没有看懂，为什么返回a[k]。快速选择没有保证序列的顺序，为什么a[k]是第k小的数？

我一开始就是这个思路

这样改进OK不，望指正

#include <iostream>
using namespace std;
const int N = 1e6+10;

int n,k;
int q[N];

void quick_sort(int l,int r)
{
    //特殊情况
    if(l>=r) return;
    //分出左右
    int x=q[l+r>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    //递归处理左右
    if(k<=j) quick_sort(l,j);//if判断
    else quick_sort(j+1,r);
}
int main()
{
    scanf("%d %d",&n,&k);
    k--;//位置减去
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    quick_sort(0,n-1);

    printf("%d",q[k]);
    return 0;
}

可以用二分答案的方法 $(O(n \log t))$，其中 $t$ 为值域

点这里

好思路！！，功能一样，思路上简化不少！