非线性时间比较类

交换排序

冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换他们两个
O(n²)
稳定

void bubble_sort(vector<int> &q)
{
    for (int i = q.size()-1; i > 0; i --)
    {
        bool flag = false;
        for (int j = 0; j + 1 <= i; j ++)
        {
            if (q[j] > q[j+1])
            {
                swap(q[j], q[j+1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

快速排序

最差：O(n²)；平均：O(nlogn)

void quick_sort(vector<int> &q, int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = q[(l + r) / 2];
    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(q, l, j), quick_sort(q, j+1, r);
}

快速选择

int quick_sort(int l, int r, int k)
{
   if (l == r) return q[l];
   int x = q[(l + r) / 2], 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]);
   }
   int sl = j - l + 1;
   if (k <= sl) return quick_sort(l, j, k);
   else return quick_sort(j+1, r, k-sl);
}

插入排序

在已排序序列中从后向前扫描，找到相应的位置并插入
O(n²)
稳定

void insert_sort(vector<int> &q)
{
    for (int i = 1; i < q.size(); i ++)
    {
        int t = q[i], j;
        for (j = i-1; j >= 0; j --)
        {
            if (q[j] > t) q[j + 1] = q[j];
            else break;
        }
        q[j + 1] = t;
    }
}

简单插入排序

选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾
O(n²)
稳定

void select_sort(vector<int> &q)
{
    for (int i = 0; i < q.size(); i ++)
    {
        for (int j = i; j < q.size(); j ++)
        {
            if (q[i] > q[j]) swap(q[i], q[j]);
        }
    }
}

简单选择排序

堆排序

O(nlogn)

# include <iostream>
# include <cstring>
# include <algorithm>
# include <cstdio>
# include <vector>

using namespace std;

void down(vector<int> &heap, int size, int u)
{
    int t = u; // 根节点和两个儿子之间的最小值
    int left = u * 2, right = u * 2 + 1;
    if (left <= size && heap[left] > heap[t]) t = left;
    if (right <= size && heap[right] > heap[t]) t = right;
    if (t != u)
    {
        swap(heap[u], heap[t]);
        down(heap, size, t);
    }

}

void up(vector<int> &heap, int u)
{
    while (u / 2 && heap[u / 2] < heap[u])
    {
        swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}

void insert(vector<int> &heap, int size, int x)
{
    heap[++ size] = x;
    up(heap, x);
}

void pop(vector<int> &heap, int size, int x)
{
    heap[1] = heap[size];
    size --;
    down(heap, size, 1);
}

void heap_sort(vector<int> &heap, int n)
{
    int size = n;
    for (int i = 1; i <= n; i ++) up(heap, i);
    for (int i = 1; i <= n; i ++)
    {
        swap(heap[1], heap[size]);
        size --;
        down(heap, size, 1);
    }
}

int main()
{
    vector<int> q;
    int n;
    cin >> n;
    q.resize(n + 1);
    for (int i = 1; i <= n; i ++) cin >> q[i];

    heap_sort(q, n);

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

归并排序

void merge_sort(vector<int> &q, int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2;

    merge_sort(q, l, mid), merge_sort(q, mid+1, r);

    static vector<int> w;
    w.clear();

    int i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) w.push_back(q[i ++]);
        else w.push_back(q[j ++]);
    }

    while (i <= mid) w.push_back(q[i ++]);
    while (j <= r) w.push_back(q[j ++]);

    for (i = l, j = 0; j < w.size(); i ++, j ++) q[i] = w[j];
}

二路归并排序

多路归并排序

线性时间非比较类

计数排序

将输入的数据值转化为键存储在额外开辟的数组空间中
应用：后缀数组
稳定

void counting_sort(vector<int> &q, int n)
{
    vector<int> cnt(101, 0);

    for (int i = 1; i <= n; i ++) cnt[q[i]] ++;

    for (int i = 1, k = 1; i <= 100; i ++)
    {
        while (cnt[i])
        {
            q[k ++] = i;
            cnt[i] --;
        }
    }
}

桶排序

计数排序的升级版，运用了函数的映射关系

基数排序

特殊的桶排序

int get(int x, int i) // 取当前数的第几位
{
    while (i --) x /= 10;
    return x % 10;
}

void radix_sort(vector<int> &q, int n)
{
    vector<vector<int>> cnt(10);
    for (int i = 0; i < 3; i ++)
    {
        for (int j = 0; j < 10; j ++) cnt[j].clear();
        for (int j = 1; j <= n; j ++) cnt[get(q[j], i)].push_back(q[j]);
        // k：当前要放第几个数
        for (int j = 0, k = 1; j < 10; j ++)
        {
            for (int x : cnt[j]) q[k ++] = x;
        }
    }
}