2025-01-18快速排序

快速排序

模板

int n;
int a[N];

void qs(int l,int r){
    if(l>=r) return;//判断递归退出
	int x=a[(l+r)/2],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]);
    }
    qs(l,j);//注意j不能漏
    qs(j+1,r);
}

qs(0,n-1);

例题

【1.基础算法-模板】1.快速排序 （模板）_快速排序算法模板-CSDN博客

//快速排序
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n;
int a[N];

void qs(int l,int r){
    if(l>=r) return;
	int x=a[(l+r)/2],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]);
    }
    qs(l,j);
    qs(j+1,r);
}

void work(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    qs(0,n-1);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}

int main(){
    work();
    return 0;
}

//第k个数
#include <bits/stdc++.h>
using namespace std;

int n, k;
const int N = 1e5 + 5;
int a[N];

int find_k(int l, int r, int k)
{
    if (l >= r)
        return a[l];
    int x = a[l + (r - l) / 2], 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]);
    }

    int len = j - l + 1;
    if (len >= k)
        return find_k(l, j, k);
    else
        return find_k(j + 1, r, k - len);
}

void work()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int find = find_k(0, n - 1, k);
    cout << find << endl;
}

int main()
{
    work();
    return 0;
}