第k个数

发现y总的快排模版(如下所示)无法保证j处的分解点在解决后续(子数组排序)问题时保持不变。换句话说，它仅能保证arr[l, j] <= pivot, arr[j+1, r] >= pivot。那如果进一步保证arr[j] == pivot，那直接判断 j == k即可解决问题。

快排模版

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int arr[N];
int n;

void quick_sort(int arr[], int l, int r)
{
    if(l >= r) return ;

    int i = l-1, j = r+1, pivot = arr[l+r>>1];
    do
    {
        do i++; while(arr[i] < pivot);
        do j--; while(arr[j] > pivot);
        if(i < j) {int t = arr[i]; arr[i] = arr[j]; arr[j] = t;}
    }while(i < j);

    // 跳出循环的条件：
    // arr[l, i-1] <= pivot, arr[i] >= pivot
    // arr[j+1, r] >= pivot, arr[j] <= pivot
    // i >= j

    // 可以得到：
    // arr[l, j] <= pivot, arr[j+1, r] >= pivot
    quick_sort(arr, l, j);
    quick_sort(arr, j+1, r);
}

int main(void)
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &arr[i]);
    }

    quick_sort(arr, 0, n-1);

    for(int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    return 0;
}

快速选择

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int arr[N];

int n, k;

void quick_select(int arr[], int l, int r, int k)
{
    if(l >= r) return ; 

    int i = l, j = r, pivot = arr[l];
    do
    {
        do i++; while(i < r && arr[i] < pivot);
        do j--; while(j > l && arr[j] > pivot);
        if(i < j) {int t = arr[i]; arr[i] = arr[j]; arr[j] = t;}
    }while(i < j);
    // 跳出循环的条件：
    // arr[l+1, i-1] <= pivot arr[i] >= pivot
    // arr[j+1, r-1] >= pivot arr[j] <= pivot
    // i >= j 
    // 可以得到：
    // arr[l+1, j] <= pivot, arr[j+1, r-1] >= pivot

    int t = arr[l]; arr[l] = arr[j]; arr[j] = t;
    // 可以得到：
    // arr[l, j-1] <= pivot, arr[j] = pivot, arr[j+1, r-1] >= pivot

    if(j > k)
        quick_select(arr, l, j, k);
    else if(j < k)
        quick_select(arr, j+1, r, k);
    else
    {
        printf("%d\n", arr[j]);
        return ;
    }
}

int main(void)
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);

    quick_select(arr, 0, n, k-1);
    return 0;
}

时间复杂度

$O(N)$

参考文献

快排分析:
https://www.acwing.com/solution/content/16777/

值得注意的是，这个普通的思想是教材上讲快排的，但是用在这里方便很多。