Radix Sort

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 31623;

int a[N], t[N], p[M], n;
void radix_sort(int digits, int r) {
    int radix = 1;
    for (int i = 0; i < digits; ++i) {
        memset(p, 0, sizeof p);
        for (int i = 0; i < n; ++i) ++p[a[i] / radix
        for (int i = 1; i < M; ++i) p[i] += p[i - 1];
        for (int i = n - 1; i >= 0; --i) t[--p[a[i] / radix
        for (int i = 0; i < n; ++i) a[i] = t[i];
        radix *= r;
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    radix_sort(3, M);
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    return 0;
} 

Merge Sort

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int a[N], t[N], n;
void merge_sort(int left, int right) {
    if (left >= right) return ;
    int mid = ((right - left) >> 1) + left;
    merge_sort(left, mid), merge_sort(mid + 1, right);
    int l = left, r = mid + 1, idx = l;
    while(l <= mid && r <= right) {
        if (a[l] < a[r]) t[idx++] = a[l++];
        else t[idx++] = a[r++];
    }
    while(l <= mid) t[idx++] = a[l++];
    while(r <= right) t[idx++] = a[r++];
    for (int i = left; i <= right; ++i) a[i] = t[i];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    merge_sort(0, n - 1);
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    return 0;
} 

Quick Sort

#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int a[N], n;
void quick_sort(int left, int right) {
    if (left >= right) return;
    int l = left - 1, r = right + 1, tar = a[((r - l) >> 1) + l];
    while(l < r) {
        do ++l; while(a[l] < tar);
        do --r; while(a[r] > tar);
        if (l < r) swap(a[l], a[r]);
    }
    quick_sort(left, r), quick_sort(r + 1, right);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    quick_sort(0, n - 1);
    for (int i = 0; i < n; ++i) cout << a[i] << ' ';
    return 0;
} 
分类: AlgorithmSort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status