1.为什么这个快排是错的？

#include<bits/stdc++.h>
using namespace std;

int n,x[1005];

void Qsort(int l,int r)
{
	int i,j;
	if(l>=r) return;
	int d=(int)(1.0*rand()/RAND_MAX+1LL);
	swap(x[l],x[d]);
	for(i=j=l+1;i<=r;i++)
		if(x[i]<x[l])
			swap(x[j++],x[i]);
	swap(x[l],x[j-1]);
	Qsort(l,j-2);
	Qsort(j,r);		
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>x[i];
	Qsort(0,n-1);
	for(int i=0;i<n;i++)
		cout<<x[i]<<" ";	
	return 0;
}

2.现在遇到了一个问题：求一个数组中第k小的元素。

$n$<=3$$*$$10^6,$ai$<=$10^9$

(也就是时间复杂度为$O$($n$),不允许使用桶排，归并，堆；要使用快排，边做边判断)

悬赏关注！