快速排序
786.第k个数
快排板子
1.选择分界点x
2.调整范围
3.递归排序
void quick_sort(int q[],int l,int r) // 将q[l]-q[r]排序直到l >= r(等价于l==r)
{
if( l >= r ) return;
int x = q[(l+r) >> 1] , i = l - 1 , j = r + 1;
while( i < j )
{
while(q[++i] < x);
while(q[--j] > x);
if(i < j) swap(q[i],q[j]); // 可以具体举例模拟过程
}
quick_sort(q,l,j) , quick_sort(q,j+1,r); // <l--j>(全部小于等于x) <j+1--r>(全部大于x)
}
解题思路(快速选择算法) $O(nlogn) ➡️ O(n)$
先判断k处于两个区间中的哪一个,只需递归排序k所在区间,降低时间复杂度。
题解代码
#include <iostream>
using namespace std;
const int N = 100010;
int n,k;
int q[N];
int quick_sort(int l,int r,int k)
{
if(l >= r) return q[l];
int x = q[(l+r) >> 1] , i = l - 1 , j = r + 1;
while( i < j )
{
while(q[++i] < x );
while(q[--j] > x );
if(i < j) swap(q[i],q[j]);
} // 上板子
int sl = j - l + 1; // 左区间元素个数
if(k <= sl) return quick_sort(l,j,k); // k <= sl (k在左区间)
return quick_sort(j+1,r,k-sl);
// 注意边界处理
// *point : 一直以k为界限,最后剩下的数就是排序后第k个数,return q[0]。
}
int main()
{
cin >> n >> k;
for(int i = 0 ; i < n ; ++i) scanf("%d",&q[i]);
cout << quick_sort(0,n-1,k) << endl;
return 0;
}