十种排序算法

• 冒泡排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            if (a[j] > a[j + 1])//冒泡
                swap(a[j], a[j + 1]);

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 快速排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
void quickSort(int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[(i + j) >> 1];
    while (i < j) {
        do i++; while(a[i] < x);
        do j--; while(a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quickSort(l, j);
    quickSort(j + 1, r);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    quickSort(1, n);

    for (int i = 1; i <= n; i++) 
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 插入排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 2; i <= n; i++)
    {
        int j = i - 1;
        while (j >= 1 && a[j + 1] < a[j]) 
            swap(a[j + 1], a[j]), j--;
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 希尔排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int d = n / 2; d >= 1; d /= 2)
    {
        for (int i = d + 1; i <= n; i++)
        {
            int j = i - d;
            while (j >= 1 && a[j + d] < a[j])
                swap(a[j + d], a[j]), j -= d;
        }
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 选择排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i < n; i++)
    {
        int k = i;
        for (int j = i + 1; j <= n; j++)
            if (a[j] < a[k]) k = j;
        swap(a[i], a[k]);
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 堆排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n;
int a[N];
int heap[N], idx;
void up(int u)
{
    while (u / 2 > 0 && heap[u] < heap[u / 2])
        swap(heap[u], heap[u / 2]), u /= 2;
}
void down(int u)
{
    int t = u;
    if (u * 2 <= idx && heap[u * 2] < heap[t]) t = u * 2;
    if (u * 2 + 1 <= idx && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (t == u) return;
    swap(heap[u], heap[t]);
    down(t); 
}
void insert(int x)
{
    heap[++idx] = x;
    up(idx);
}
void pop()
{
    swap(heap[1], heap[idx]);
    --idx;
    down(1);
}
inline int top() { return heap[1]; }
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) insert(a[i]);
    for (int i = 1; i <= n; i++)
    {
        a[i] = top();
        pop();
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 归并排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N], b[N];
void mergeSort(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    mergeSort(l, mid), mergeSort(mid + 1, r);
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++)
    {
        if (j > r || (i <= mid && a[i] < a[j]))
            b[k] = a[i++];
        else 
            b[k] = a[j++];
    }
    for (int k = l; k <= r; k++) a[k] = b[k];
}
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    mergeSort(1, n);

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 计数排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N], b[N];
int main() {
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    vector<int> c(mx + 1);
    for (int i = 1; i <= n; i++) c[a[i]]++;
    for (int i = 1; i <= mx; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) b[c[a[i]]--] = a[i];

    for (int i = 1; i <= n; i++) 
        cout << b[i] << " \n"[i == n];

    return 0;
}

---

• 基数排序、

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N], b[N], c[10];
int main() {
    cin >> n;
    int mx = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        int t = a[i], tot = 0;
        while (t) t /= 10, tot++;
        mx = max(mx, tot);
    }

    for (int k = 0, base = 1; k < mx; k++, base *= 10)
    {
        for (int i = 0; i < 10; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[a[i] / base % 10]++;
        for (int i = 1; i < 10; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--)
            b[c[a[i] / base % 10]--] = a[i];
        for (int i = 1; i <= n; i++) a[i] = b[i];
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];

    return 0;
}

---

• 桶排序

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, a[N];
int main() {
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    vector<vector<int>> b(mx / 10 + 1);
    for (int i = 1; i <= n; i++) b[a[i] / 10].push_back(a[i]);
    for (int i = 0; i <= mx / 10; i++) 
        sort(b[i].begin(), b[i].end());

    for (int i = 0; i <= mx / 10; i++)
        for (auto x : b[i])
            cout << x << " ";

    return 0;
}