记录一些算法模板

MISC

IO 优化 (LeetCode)

int init_io = []{
    ios::sync_with_stdio(false);
    return 0;
}();

排序

稳定性

• 不稳定: 堆排序、快速排序、希尔排序、直接选择排序
• 稳定: 冒泡排序、直接插入排序、折半插入排序、归并排序

快速排序

上机 ver.

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

单链表 ver.

class Solution {
public:
    ListNode* quickSortList(ListNode* head) {
        if (!head) return head;
        
        ListNode *l = nullptr, *r = nullptr, *pivot = head;
        head = head->next;
        
        while (head) {
            auto t = head;
            head = head->next;
            
            if (pivot->val < t->val) t->next = r, r = t;
            else t->next = l, l = t;
        }
        
        l = quickSortList(l);
        r = quickSortList(r);
        
        pivot->next = r;
        if (l == nullptr) {
            return pivot;
        } else {
            auto ll = l;
            while (ll->next) ll = ll->next;
            ll->next = pivot;
            return l;
        }
    }
};

希尔排序

可能比快排优, 数据基本有序情况下
O(n ** 1.3)

void shell_sort() 
{
    for (int d = n / 3; d; d = (d == 2) ? 1 : d / 3) {
        for (int start = 0; start < d; start++)
            for (int i = start + d; i < n; i += d) {
                // 直接插入排序
                int t = w[i], j = i;
                while (j > start && w[j - d] > t)
                    w[j] = w[j - d], j -= d;
                w[j] = t;
            }
    }
}

冒泡排序

void bubble_sort()
{
    for (int i = 0; i < n - 1; i ++ )
    {
        bool has_swap = false;
        for (int j = n - 1; j > i; --j)
            if (w[j - 1] > w[j])
            {
                swap(w[j - 1], w[j]);
                has_swap = true;
            }
        if (!has_swap) break;
    }
}

插入排序

void insert_sort()
{
    for (int i = 1; i < n; i ++ ) {
        int t = w[i], j = i;
        while (j && w[j - 1] > t)
            w[j] = w[j - 1], --j;
        w[j] = t;
    }
}

折半插入

void binary_search_insert_sort() // 折半插入
{
    for (int i = 1; i < n; i++) {
        if (w[i - 1] <= w[i]) continue;
        
        int t = w[i];
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = l + r >> 2;
            if (w[mid] > t) r = mid;
            else l = mid + 1;
        }
        
        for (int j = i - 1; j >= r; --j)
            w[j + 1] = w[j];
        w[r] = t;
    }
}

归并排序

void merge_sort(int l, int r)
{
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(l, mid); merge_sort(mid + 1, r);
    
    // Merge two seg
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        q[k++] = (w[i] < w[j]) ? w[i++] : w[j++];
    while (i <= mid) q[k++] = w[i++];
    while (j <= r) q[k++] = w[j++];
    
    // Copyback
    for (int i = 0; i < k; i++)
        w[i + l] = q[i];
}

外部排序

• 归并
• 胜者树与败者树

字符串

KMP

AcWing 831

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
const int N = 1e6 + 10;
int ne[N];
char p[N], s[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) ++j;
        ne[i] = j;
    }
    
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) ++j;
        
        if (j == n) cout << i - n << ' ';
    }
    
    return 0;
}