快速排序 & 归并排序

快速排序

思想：分治

基准点的选取可以是数组里随便一个元素。

时间复杂度：O((nlog{n}))

https://www.luogu.com.cn/record/46587228

坑：如果永远取第一个元素作为枢轴的话，在数组已经有序的情况下每次划分都将得到最坏的结果，时间复杂度退化为O(n^2)。

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

#define Mid ((l + r) >> 1)

const char nl = '
';
const int N = 1e5 + 50;

int n;
int q[N];

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

    int x = q[Mid]; // x = q[l] 和 x = q[r] 也可以
    int i = l - 1, j = r + 1;
    while (i < j){
        do ++i; while (q[i] < x);
        do --j; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    
    quick_sort(0, n - 1);
    
    for (int i = 0; i < n; ++i) cout << q[i] << ' ';
    return 0;
}

归并排序

思想：分治

时间复杂度：O((nlog{n}))

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

#define Mid ((l + r) >> 1)

const char nl = '
';
const int N = 1e5 + 50;

int n;
int q[N], tmp[N];

void merge_sort(int l, int r){
    if (l >= r) return ;

    merge_sort(l, Mid);
    merge_sort(Mid + 1, r);

    int tot = 0;
    int i = l, j = Mid + 1;
    while (i <= Mid && j <= r){
        if (q[i] <= q[j]) tmp[tot++] = q[i++];
        else tmp[tot++] = q[j++];
    }
    while (i <= Mid) tmp[tot++] = q[i++];
    while (j <= r) tmp[tot++] = q[j++];

    for (int i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];

    merge_sort(0, n - 1);

    for (int i = 0; i < n; ++i) cout << q[i] << ' ';
    return 0;
}