信息学竞赛模板（四）— 快速选择（排序）

2021-02-14 · 98次阅读 · 原创 · 数据结构与算法

快速排序

利用分治的思想，在 [l, r] 中随机选取一个基准值，将其他位置的数与基准值相比较，若比基准值小，放到基准值位置的左边，否则放在基准值位置的右边，再递归基准值左边区间和基准值右边区间，又进行上述操作，直到区间大小为2时，则直接比较两个元素的大小位置进行位置交换，区间大小为1时，直接返回该区间。最后整个区间即为排好序的。

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

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

    int i = l, j = r;
    while (i < j) {
        while (i < j && key < a[j]) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] < key) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = key;

    quick_sort(l, i - 1);
    quick_sort(i + 1, r);
}

数据加强版，分界点需取中间

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

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

快速选择

同快速排序的思想。例如，输出一个数列排序后的第 k 个位置上的数（第k个数）。

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 1e5 + 5;

int n, k;
int a[MAX];

int divide(int l, int r, int k) {
    int key = a[l];
    if (l == r) return key;

    int i = l, j = r;
    while (i < j) {
        while (i < j && key < a[j]) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
        while (i < j && a[i] < key) i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = key;

    if (i - l + 1 == k) return key;
    if (i - l >= k) return divide(l, i - 1, k);
    return divide(i + 1, r, k - (i - l + 1));
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i + 1]);
    }

    cout<<divide(1, n, k)<<endl;

    return 0;
}

标题：	信息学竞赛模板（四）— 快速选择（排序）
链接：	https://www.fightingok.cn/detail/50
更新：	2022-09-18 22:34:30
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可

信息学竞赛模板（四）— 快速选择（排序）

快速排序

快速选择

Cyan