经典数据结构与算法

经典数据结构

向量 Vector

​x
#define DEFAULT_CAPACITY X
using Data = int;

class Vector {
private:
    int _size;
    int _capacity;
    Data* _elem;
public:
    Data& operator[](int r) { return _elem[r]; }
    
    void expand(); // amortized: O(1)
    void insert(int r, Data const& e);
    void remove(int lo, int hi); 
    
    void sort(); // O(nlogn)
    int find(Data& e, int lo, int hi) { // O(n)
        while ((lo < hi--) && (e != _elem[hi]));
        return hi;
    }
    int search(Data& e); // O(logn)
}; // S(n)

列表 List

xxxxxxxxxx
struct Node {
    int data;
    Node* pred;
    Node* succ;
}

class List {
private:
    int _size;
    Node* head, tail;
public:
    List() {};
    void insert(int r, Node* e); // O(1)
    void remove(int r); // O(n)
}; // S(n)

栈 Stack

xxxxxxxxxx
class Stack {
private:
    int size = 0;
    Node* nodes[MAXN];
public:
    void push(Node* e) { nodes[size++] = e; } // O(1)
    Node* pop() { return nodes[--size]; } // O(1)
    Node* top() { return nodes[size - 1]; } // O(1)
    bool empty() { return size == 0; }
}; // S(n)

队列 Queue

xxxxxxxxxx
class Queue {
private:
    int size = 0;
    Node* head;
    Node* tail;
public:
    Queue() {
        head = new Node(); tail = new Node();
        head->succ = tail; tail->pred = head;
    }
    void enqueue(Node* e) { // O(1)
        size++;
        e->succ = tail;
        e->pred = tail->pred;
        tail->pred->succ = e;
        tail->pred = e;
    }
    Node* dequeue() { //O(1)
        size--;
        Node* ret = head->succ;
        head->succ = ret->succ;
        ret->succ->pred = head;
        return ret;
    }
    Node* top() { return head->succ; } // O(1)
    bool empty() { return size == 0; }
}; // S(n)

Steap (Stack + Heap)

xxxxxxxxxx
class Steap {
private:
    Stack S, P;
public:
    Node* getMax() { return P.top(); } // O(1)
    void push(Node* e) { // O(1)
        P.push( max(e, P.top()) );
        S.push(e);
    }
    Node* pop() { // O(1)
        P.pop();
        return S.pop();
    }
}; // S(2n)

Queap (Queue + Heap)

xxxxxxxxxx
class Queap {
private:
    Queue Q, P;
public:
    Node* getMax() { return P.top(); } // O(1)
    void enqueue(Node* e) { // O(n)
        P.enqueue(e);
        Q.enqueue(e);
        for (Node* x = P.tail; x && (x->data <= e); x = x->pred)
            x->data = e;
    }
    Node* dequeue() { // O(1)
        P.dequeue();
        return Q.dequeue();
    }
}; // S(2n)

BBST

1. AVL

xxxxxxxxxx
struct Node {
    int data; int height;
    Node* parent;
    Node* lc; Node* rc;
    Node(int e = -1) : data(e), height(0) {};
    Node* succ();
};

class AVL {
private:
    int _size = 0;
    Node* _root;
    Node* _hot;
protected:
    bool isLChild(Node* x);
    Node* tallerChild(Node* x);
    bool avlBalanced(Node* x);
    void updateHeight(Node* x);
    Node* search(const int& e); // O(logn)
    void removeAt(Node* x, Node* hot);
    Node* connect34(Node* a, Node* b, Node* c, Node* t0, Node* t1, Node* t2, Node* t3);
    Node* rotateAt(Node* v);
    void processImbalance(Node* g);
    
public:
    AVL() : _root(nullptr), _hot(nullptr) {};
    void insert(const int& e) { // O(logn)
        Node* x = search(e);
        if (x) return;
        _size++;
        if (_hot == nullptr) _root = new Node(e);
        else {
            Node* node = new Node(e);
            (e < _hot->data) ? _hot->lc = node : _hot->rc = node;
            node->parent = _hot;
        }
        for (Node* g = _hot; g != nullptr; g = g->parent) {
            if (!avlBalanced(g)) {
                processImbalance(g);
                break;
            }
            else updateHeight(g);
        }
    }
    void remove(const int& e) { // O(logn)
        Node* x = search(e);
        removeAt(x, _hot);
        _size--;
        for (Node* g = _hot; g != nullptr; g = g->parent) {
            if (!avlBalanced(g)) {
                processImbalance(g);
            }
            updateHeight(g);
        }
    }
}

2. B树

xxxxxxxxxx
const int M = 7;
const int T = 4;

class Node {
private:
    int* keys;
    Node** childrens;
    int num;
    bool leaf;
public:
    Node(bool isleaf) {
        keys = new DATA[M - 1];
        childrens = new Node* [M];
    }
    void insertNonFull(int v) {
        int i = num - 1;
        if (leaf) {
            while (i >= 0 && keys[i] > v) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = v;
            num++;
        }
        else {
            while (i >= 0 && keys[i] > v) i--;
            if (childrens[i + 1]->num == M - 1) {
                splitChild(i + 1, childrens[i + 1]);
                if (keys[i + 1] < v) i++;
            }
            childrens[i + 1]->insertNonFull(v);
        }
    }
    void splitChild(int i, Node* y);
    void traverse() {
        for (int i = 0; i < n; ++i) {
            if (leaf == false)
                childrens[i]->traverse();
            cout << " " << keys[i];
        }
    }
    Node* search(int v) { // O(logn)
        int i = 0;
        while (i < n && v > keys[i]) i++;
        if (i < n && keys[i] == v) return this;
        if (leaf) return NULL;
        return childrens[i]->search(v);
    }
    friend class BTree;
};

class BTree {
private:
    Node* root;
public:
    void traverse() { if (root) root->traverse(); }
    Node* search(int v) { return root ? root->search(v) : NULL; }
    void insert(int v) { // O(logn)
        if (!root) {
            root = new Node(true);
            root->keys[0] = v;
            root->num = 1;
        }
        else {
            if (root->num == M - 1) {
                Node* S = new Node(false);
                S->childrens[0] = root;
                S->splitChild(0, root);
                int i = 0;
                if (S->keys[0] < v) i++;
                S->childrens[i]->insertNonFull(v);
                root = S;
            }
            else root->insertNonFull(v);
        }
    }
    void delete(int v); // O(logn)
};

3. Red-Black Tree

xxxxxxxxxx
class RedBlack { // Notation: [rotate, recolor, done]
protected:
    void solveDoubleRed(Node* x) {
        if (isRoot(*x)) {
            _root->color = BLACK;
            _root->height++;
            return;
        }
        Node* p = x->parent;
        if (isBlack(p)) return;
        Node* g = p->parent;
        Node* u = uncle(x);
        if (isBlack(u)) // RR-1: u->color == B [1~2, 2, √]
        else // RR-2: u->color == R [0, 3, ×]
    }
    void solveDoubleBlack(Node* r) {
        Node* p = r ? r->parent : _hot;
        if (!p) return;
        Node* s = (r == p->lc) ? p->rc : p->lc;
        if (isBlack(s)) {
            Node* t = nullptr;
            if (isRed(s->rc)) t = s->rc;
            if (isRed(s->lc)) t = s->lc;
            if (t) // BB-1: s->c == R [1~2, 3, √]
            else {
                s->color = RED;
                s->height--;
                if (isRed(p)) // BB-2R: s->c == Bs, p == R [0, 2, √]
                else {// BB-2B: s->c == Bs, p == B [0, 1, ×]
                    p->height--;
                    solveDoubleBlack(p);
                }
            }
        }
        else // BB-3: s == R [1, 2, ×]
    }
    int updateHeight(Node* x) {
        return x->height = isBlack(x) + max(stature(x->lc), stature(x->rc));
    }
public:
    void insert(const int& e) { // O(logn)
        Node* x = search(e);
        if (x) return;
        x = new Node(e, _hot, NULL, NULL, 0);
        _size++;
        solveDoubleRed(x);
    }
    void remove(const int& e) { // O(logn)
        Node* x = search(e);
        if (!x) return;
        Node* r = removeAt(x, _hot); 
        if (!(--_size)) return;
        if (!_hot) {
            _root->color = BLACK;
            updateHeight(_root);
            return;
        } 
        if (blackHeightUpdated(*_hot))
        if (isRed(r)) {
            r->color = BLACK;
            r->height++;
            return;
        }
        solveDoubleBlack(r);
    }
};

4. Splay Tree

xxxxxxxxxx
class Splay {
protected:
    Node* splay(Node* v) {
        if (!v) return nullptr;
        Node* p, g;
        while ((p = v->parent) && (g = p->parent)) {
            Node* gg = g->parent;
            if ( IsLChild( * v ) )
                if ( IsLChild( * p ) ) // zig-zig 
                else // zig-zag
            else
                if ( IsRChild( * p ) ) // zag-zag  
                else // zag-zig
            if ( !gg ) v->parent = nullptr;
            else ( g == gg->lc ) ? attachAsLC(v, gg) : attachAsRC(gg, v);
            updateHeight(g); updateHeight(p); updateHeight(v);
        }
    }
public:
    Node* search(const int& e) {
        Node* p = BST::search(e);
        _root = splay(p ? p : _hot);
        return _root;
    }
    void insert(const int& e) {
        if (!_root) {
            _size = 1;
            _root = new Node*(e);
            return;
        }
        Node* t = search(e);
        if (e == t->data) return;
        if (t->data < e) // _root->lc = t
        else // _root->rc = t
        _size++; updateHeightAbove(t);
    }
    void remove(const int& e) {
        if (!_root || (e != search(e)->data)) return;
        Node* L = _root->lc, R = _root->rc;
        release(_root);
        if (!R) {
            if (L) L->parent = NULL;
            _root = L;
        }
        else {
            _root = R;
            R->parent = NULL;
            search(e); // from R
            if (L) L->parent = _root;
            _root->lc = L;
        }
    }
};

跳转表 Skip List

xxxxxxxxxx
struct QNode {
    int data;
    QNode* pred, succ, above, below;
    QNode* insert(int const& e, QNode* b = NULL);
};
struct QuadList {
    int _size;
    QNode* header, trailer;
    void remove(QNode* p);
    void insert(int const& e, QNode* p, QNode* b = NULL);
};
struct SkipList : public Dictionary<int, int>, public List<QuadList<Entry<int, int>>*> {
    QNode* search(int key); // expected-O(logn)
    int size();
    int height() { return List::size(); }
    void put(int key, int value); // expected-O(logn)
    int* get(int key);
    bool remove(int key); // expected-O(logn)
};

图 Graph

xxxxxxxxxx
using VStatus = enum { UNDISCOVERED, DISCOVERED, VISITED };
struct Vertex {
    int data; int inDegree, outDegree;
    VStatus status;
    int dTime, fTime;
    int parent;
    int priority; 
    Vertex(int const& d) : data(d), status(UNDISCOVERED), dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
};

using EType = enum {UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD};
struct Edge {
    int data; 
    int weight; 
    EType type; 
    Edge(int const& d, int w) : data(d), weight(w), type(UNDETERMINED) {}
};

class GraphMatrix { // adjacency matrix
private:
    int n, e;
    Vector<Vertex> V;
    Vector<Vector<Edge>*> E;
public:
    void insertEdge(int const& edge, int w, int v, int u) {
        if (exists(v, u)) return;
        E[v][u] = new Edge(edge, w); e++;
        V[v].outDegree++;
        V[u].inDegree++;
    }
    void insertVertex(int const& vertex);
    void removeEdge(int v, int u);
    void removeVertex(int v);
}

并查集 DSU

Disjoint Set Union

xxxxxxxxxx
struct dsu {
    vector<int> parent;
    dsu(int size) : parent(size) { for (int i = 0; i < size; ++i) parent.put(i); }
    int find(int x) { return parent[x] == x ? x : find(parent[x]); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    void unite(int x, int y) { parent[find(x)] = find(y); }
    void erase(int x) {
        --size[find(x)]; // vector<int> parent, size;
        parent[x] = x;
    }
};

时间复杂度：$O(\alpha (n))$$O(\alpha(n))$，其中$\alpha$$\alpha$表示Ackermann函数的反函数，单词操作平均运行时间接近于一个很小的常数

优先级队列（interface） Priority Queue

xxxxxxxxxx
struct PQ {
    virtual void insert(int x) = 0;
    virtual int getMax() = 0;
    virtual int delMax() = 0;
};

完全二叉堆 Complete Heap

xxxxxxxxxx
#define Parent(i) ( ((i) - 1) >> 1 ) // _root = 0
#define LChild(i) ( 1 + ((i) << 1) )
#define RChild(i) ( (1 + (i)) << 1)

class ComplHeap : public PQ, public Vector<int> {
protected:
    int percolateDown(int* A, int n, int i) { // O(logn)
        int j;
        while (i != (j = ProperParent(A, n, i))) {
            swap(A[i], A[j]);
            i = j;
        }
        return i;
    }
    int percolateUp(int* A, int i) { // O(logn)
        while (0 < i) {
            int j = Parent(i);
            if (A[i] < A[j]) break;
            swap(A[i], A[j]);
            i = j;
        }
        return i;
    }
    void heapify(int* A, int n) { // Floyd: O(n)
        for (int i = n / 2 - 1; 0 <= i; --i) percolateDown(A, n, i);
    }
public:
    ComplHeap(int* A, int n) { copyFrom(A, 0, n); heapify(_elem, n); }
    void insert(int x) { Vector::insert(x); percolateUp(_elem, _size - 1); }
    int getMax() { return _elem[0]; }
    void delMax() { _elem[0] = _elem[--_size]; percolateDown(_elem, _size, 0); }
}

锦标赛树 Tournament Tree

xxxxxxxxxx
// Winner Tree
#define Parent(i) ( ((i) - 1) >> 1 ) // _root = 0
class TournamentTree {
private:
    vector<int> tree;
    int n;
public:
    TournamentTree(const vector<int>& elements) { // O(n)
        n = elements.size();
        int tree_size = 2 * n - 1;
        tree.resize(tree_size, INT_MAX);
        for (int i = 0; i < n; i++) tree[n - 1 + i] = elements[i];
        for (int i = n - 2; i >= 0; i--) tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    }
    int findMin() { return tree[0]; } // O(1)
    void update(int i, int new_val) { // O(logn)
        int index = n - 1 + i;
        tree[index] = new_val;
        while (index > 0) {
            index = Parent(index);
            tree[index] = min(tree[2 * index + 1], tree[2 * index + 2]);
        }
    }
};

// Loser Tree
#define Parent(x) = ((i) >> 1) // _root(winner) = 0
class TournamentTree {
private:
    vector<int> tree;
    int n ;
public:
    TournamentTree(const vector<int>& elements); // O(n)
    int findMin() { return tree[0]; } // O(1)
    void update(int i, int new_val) { // O(logn)
        int index = n + i; 
        tree[index] = new_val;
        int cur_val = new_val;
        while (index > 0) {
            if (tree[Parent(index)] < cur_val) {
                swap(tree[Parent(index)], cur_val); // swap(&, &)
                index = Parent(index);
            }  
            else index = Parent(index);
        }
        tree[0] = cur_val;
    }
};

左式堆 Left Heap

xxxxxxxxxx
class LeftHeap : public PQ, public BinTree {
public:
    int getMax() { return _root->data; }
    void insert(int e) { // O(logn)
        _root = merge(_root, new Node(e, nullptr));
        _size++;
    }
    void delMax() { // O(logn)
        Node* lHeap = _root->lc;
        if (lHeap) lHeap->parent = nullptr;
        Node* rHeap = _root->rc;
        if (rHeap) rHeap->parent = nullptr;
        delete _root;
        _size--;
        _root = merge(lHeap, rHeap);
    }
    LeftHeap(LeftHeap& A, LeftHeap& B) {
        _root = merge(A._root, B._root);
        _size = A._size + B._size;
        A._root = B._root = nullptr;
        A._size = B._size = 0;
    }
};

Node* merge(Node* a, Node* b) { // O(logn)
    if (!a) return b;
    if (!b) return a;
    if (a->data < b->data) swap(a, b);
    (a->rc = merge(a->rc, b))->parent = a;
    if (!a->lc || a->lc->npl < a->rc->npl) 
        swap(a->lc, a->rc);
    a->npl = a->rc ? 1 + a->rc->npl : 1;
    return a;
}

Node* merge(Node* a, Node* b) { // iterative version
    if (!a) return b;
    if (!b) return a;
    if (a->data < b->data) swap(a, b);
    for ( ; a->rc; a = a->rc) {
        if (a->rc->data < b->data) {
            b->parent = a;
            swap(a->rc, b);
        }
    }
    (a->rc = b)->parent = a;
    for ( ; a; b = a, a = a->parent) {
        if (!a->lc || a->lc->npl < a->rc->npl)
            swap(a->lc, a->rc);
        a->npl = a->rc ? a->rc->npl + 1 : 1;
    }
}

串 String

xxxxxxxxxx
class String {
private:
    int n;
    char S[];
public:
    String substr(int i, int k) { return String(S, i, k); } // S[i, i + k)
    String prefix(int k) { return String(S, 0, k); } // S[0, k)
    String suffix(int k) { return String(S, n - k, k); } // S[n - k, n)
    int length();
    char charAt(int i);
    String concat(String s) { return String(S, s); }
    bool equal(String s);
    int indexOf(String s) { return search(s); }
};
// <string.h>: strlen(), strcpy(), strcat(), strcmp(), strstr()...

经典算法

快速幂

求$a$$a$的$n$$n$次方

xxxxxxxxxx
int power(int a, int n) {
    int pow = 1, p = a; // O(1)
    while (0 < n) { // O(logn)
        if (n & 1) pow *= p;
        n >>= 1;
        p *= p;
    }
    return pow;
}

时间复杂度：$O(logn)$$O(logn)$

countOnes

统计整数二进制展开中数位1的总数

xxxxxxxxxx
int countOnes(unsigned int n) {
    int ones = 0;
    while (0 < n) {
        ones++;
        n &= n - 1;
    }
    return ones;
}

时间复杂度：$O(ones)$$O(ones)$，正比于数位1的总数

总和最大区段

从整数序列$A[n]$$A[n]$中，求总和最大的区段的和（有多个时，短者优先）

xxxxxxxxxx
int gs_LS(int A[], int n) {
    int gs = A[0], s = 0, i = n;
    while (0 < i--) {
        s += A[i];
        if (gs < s) gs = s;
        if (s <= 0) s = 0;
    }
    return gs;
}

时间复杂度：$O(n)$$O(n)$

斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8... 求第$n$$n$个数字（从1开始编号）

xxxxxxxxxx
int fib(int n) {
    int g = 0, f = 1;
    while (0 < n--) {
        g = g + f;
        f = g - f;
    }
    return g;
}

时间复杂度：$O(n)$$O(n)$

最长公共子序列 LCS

Longest Common Subsequence problem 求两序列（长度分别为$n$$n$和$m$$m$）最长公共子序列中的长度

xxxxxxxxxx
unsigned int lcs(char const * A, int n, char const * B, int m) {
    if (n < m) { //make sure n >= m
        swap(A, B); 
        swap(n, m); 
    } 
    unsigned int* lcs1 = new unsigned int[m + 1]; 
    unsigned int* lcs2 = new unsigned int[m + 1]; 
    memset(lcs1, 0x00, sizeof(unsigned int) * (m + 1));
    memset(lcs2, 0x00, sizeof(unsigned int) * (m + 1));
    for (int i = 0; i < n; swap(lcs1, lcs2), i++)
        for (int j = 0; j < m; j++)
            lcs2[j + 1] = (A[i] == B[j]) ? 1 + lcs1[j] : max(lcs2[j], lcs1[j + 1]);
    unsigned int solu = lcs1[m]; 
    delete[] lcs1; 
    delete[] lcs2; 
    return solu;
}

时间复杂度：$O(mn)$$O(mn)$

就地循环移位

仅用$O(1)$$O(1)$辅助空间，将数组$A[0,n)$$A[0, n)$中的元素向左循环移动$k$$k$个单位

• 迭代 时间复杂度：$O(2n)$$O(2n)$

  xxxxxxxxxx
  int shift( int* A, int n, int s, int k ) { // O(n/GCD(n, k))
      int b = A[s]; 
      int i = s, j = (s + k) % n; 
      int mov = 0; 
      while ( s != j ) { 
          A[i] = A[j]; 
          i = j; 
          j = (j + k) % n; 
          mov++; 
      }
      A[i] = b; 
      return mov + 1;
  }
  
  void shift1(int* A, int n, int k) { //O(g) = O(GCD(n, k))
      for (int s = 0, mov = 0; mov < n; s++) 
          mov += shift(A, n, s, k);
  }
  

• 倒置 时间复杂度：$O(3n)$$O(3n)$

  xxxxxxxxxx
  void shift2(int* A, int n, int k) {
      reverse(A, k); // O(3k/2)
      reverse(A + k, n - k); // O(3(n-k)/2)
      reverse(A, n); // O(3n/2)
  }
  

埃氏筛法 Eratosthenes

找出1~n中所有的素数

xxxxxxxxxx
void Eratosthenes(int n, char* file) {
    Bitmap B(n);
    B.set(0); B.set(1);
    for (int i = 2; i < n; ++i) {
        if (!B.test(i))
            for (int j = i * i; j < n; j += i) 
                B.set(j);
    }
    B.dump(file);
}

时间复杂度：$O(nlogn)$$O(nlogn)$

二分查找 BS

Binary Search 有序（可能有重）数列$S$$S$中查找指定值$e$$e$，返回不大于$e$$e$的最后一个元素。

xxxxxxxxxx
static Rank bs(T* S, T const& e, Rank lo, Rank hi) {
    while (lo < hi) {
        Rank mi = (lo + hi) >> 1;
        e < S[mi] ? hi = mi : lo = mi + 1; 
    } 
    return lo - 1;
}

时间复杂度：$O(logn)$$O(logn)$

findKth

无序数列$S$$S$中查找第$k$$k$大的元素

xxxxxxxxxx
Node nodes[MAXN];
bool cmp(Node a, Node b) { return a.data < b.data; } // NOT ≤ !
void findKth(int low, int high, bool(*cmp)(Node, Node), int k) { // [low, high], k = 1, 2, ...
    if (low == high) return;
    Node pivot = nodes[(low + high) >> 1];
    int i = low, j = high;
    i--; j++;
    while (i < j) {
        while (cmp(nodes[++i], pivot));
        while (cmp(pivot, nodes[--j]));
        if (i < j) swap(nodes[i], nodes[j]);
    }
    if (j == high) j--;
    i = j - low + 1;
    if (k <= i) return findKth(low, j, cmp, k);
    else return findKth(j + 1, high, cmp, k - i);
}

void quickSelect(Vector<int>& A, int k) { // expected-O(4n)
    for (int lo = 0, hi = A.size() - 1; lo < hi;) {
        int i = lo, j = hi;
        int pivot = A[lo];
        while (i < j) {
            while (i < j && pivot <= A[j]) j--; A[i] = A[j];
            while (i < j && A[i] <= pivot) i++; A[j] = A[i];
        } // assert: quit with i == j
        A[i] = pivot;
        if (k <= i) hi = i - 1;
        if (i <= k) lo = i + 1;
    }
}

void linearSelect(Vector<int>& A, int n, int k); // Q = 5

时间复杂度：$O(n)$$O(n)$

排序 Sort

将无序（可能有重）数列$S[lo,hi)$$S[lo, hi)$从小到大排序

1. 冒泡排序 BubbleSort

xxxxxxxxxx
void bubbleSort(int lo, int hi) { // 跳跃版
    for (int last; lo < hi; hi = last)
        for (int i = (last = lo) + 1; i < hi; ++i)
            if (S[i - 1] > S[i])
                swap(S[i - 1], S[last = i]);
}

时间复杂度：最好$O(n)$$O(n)$，最坏$O(n^2)$$O(n^2)$

2. 归并排序 MergeSort

xxxxxxxxxx
void mergeSort(int lo, int hi) {
    if (hi - lo < 2) return;
    int mi = (lo + hi) >> 1;
    mergeSort(lo, mi);
    mergeSort(mi, hi);
    merge(lo, mi, hi);
}

void merge(int lo, int mi, int hi) {
    int i = 0; int* A = S + lo; 
    int j = 0, lb = mi - lo; int* B = new int[lb]; 
    for (int t = 0; t < lb; ++t) 
        B[t] = A[t]; 
    int k = 0, lc = hi - mi; int* C = S + mi; 
    
    while ((j < lb) && (k < lc)) 
        A[i++] = (B[j] <= C[k]) ? B[j++] : C[k++];
    while (j < lb) 
        A[i++] = B[j++];
    delete [] B;
}

时间复杂度：$O(nlogn)$$O(nlogn)$

3. 选择排序 SelectionSort

xxxxxxxxxx
void selectionSort(Node* p, int n) { // [p, p + n)
    Node* head = p->pred, tail = p; 
    for (int i = 0; i < n; ++i) 
        tail = tail->succ;
    while (1 < n) { 
        insert( remove( selectMax(head->succ, n) ), tail );
        tail = tail->pred; n--;
    }
}

Node* selectMax(Node* p, int n) {
    Node* max = p;
    for (Node* cur = p; 1 < n; n--)
        if ( (cur = cur->succ)->data >= max->data )
            max = cur; 
    return max;
}

时间复杂度：$O(n^2)$$O(n^2)$，但元素移动操作显著少于冒泡排序

4. 插入排序 InsertionSort

xxxxxxxxxx
void insertionSort(Node* p, int n) {
    for (int r = 0; r < n; ++r) {
        insert( search(p->data, r, p), p->data );
        p = p->succ;
        remove(p->pred);
    } 
}

时间复杂度：最好$O(n)$$O(n)$，最坏$O(n^2)$$O(n^2)$

5. 桶排序 BucketSort

xxxxxxxxxx
const int MAXN = 1000;

int n, w, a[MAXN]; // w = max(a[n])
vector<int> bucket[MAXN];

void bucketSort() {
    int size = w / n + 1;
    for (int i = 0; i < n; ++i) bucket[i].clear();
    for (int i = 1; i <= n; ++i) bucket[a[i] / size].push_back(a[i]);
    int p = 0;
    for (int i = 0; i < n; ++i) {
        insertionSort(bucket[i], bucket[i].size());
        for (int j = 0; j < bucket[i].size(); ++j)
            a[++p] = bucket[i][j];
    }
}

时间复杂度：平均$O(n+\frac{n^2}{k}+k)\approx (n)$$O(n + \frac{n^2}{k} + k) ≈ (n)$，最坏$O(n^2)$$O(n^2)$（其中$n$$n$为数组元素数量，$k$$k$为桶数量）

6. 基数排序 RadixSort

xxxxxxxxxx
int maxBit(int data[], int n) {
    int d = 1;
    int p = 10;
    for (int i = 0; i < n; ++i) {
        while (data[i] >= p) {
            p *= 10;
            ++d;
        }
    }
    return d;
}

void radixSort(int data[], int n) {
    int d = maxBit(data, n);
    int tmp[n];
    int count[10];
    int radix = 1;
    for (int i = 1; i <= d; ++i) {
        for (int j = 0; j < 10; ++j) count[j] = 0;
        for (int j = 0; j < n; ++j) {
            int k = (data[j] / radix) % 10;
            count[k]++;
        }
        for (int j = 1; j < 10; ++j) count[j] = count[j - 1] + count[j];
        for (int j = n - 1; j >= 0; --j) {
            int k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for (int j = 0; j < n; ++j) data[j] = tmp[j];
        radix *= 10;
    }
}

时间复杂度：$O(n)$$O(n)$（若将位数$d$$d$视作常数）

7. 堆排序 HeapSort

xxxxxxxxxx
void heapSort(int lo, int hi) { // [lo, hi)
    int* A = _elem + lo;
    int n = hi - lo;
    heapify(A, n);
    while (0 < --n) {
        swap(A[0], A[n]);
        percolateDown(A, n, 0);
    }
}

时间复杂度：$O(nlogn)$$O(nlogn)$

8. 快速排序 QuickSort

• 递归版本：

  xxxxxxxxxx
  void quickSort(int lo, int hi) {
      if (hi - lo < 2) return;
      int mi = partition(lo, hi);
      quickSort(lo, mi);
      quickSort(mi + 1, hi);
  }
  
  int partition(int lo, int hi) { // LUG
      swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);
      int pivot = _elem[lo];
      while (lo < hi) {
          do { hi--; } while (lo < hi && pivot <= _elem[hi]);
          if (lo < hi) _elem[lo] = _elem[hi];
          do { lo++; } while (lo < hi && _elem[lo] <= pivot);
          if (lo < hi) _elem[hi] = _elem[lo];
      } // assert: lo == hi || hi + 1
      _elem[hi] = pivot;
      return hi;
  }
  
  int partition(int lo, int hi) { // DUP
      swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);
      int pivot = _elem[lo];
      while (lo < hi) {
          do { hi--; } while (lo < hi && pivot < _elem[hi]);
          if (lo < hi) _elem[lo] = _elem[hi];
          do { lo++; } while (lo < hi && _elem[lo] < pivot);
          if (lo < hi) _elem[hi] = _elem[lo];
      } // assert: lo == hi || hi + 1
      _elem[hi] = pivot;
      return hi;
  }
  
  int partition(int lo, int hi) { // LGU
      swap(_elem[lo], _elem[lo + rand() % (hi - lo)]);
      int pivot = _elem[lo];
      int mi = lo;
      for (int k = lo + 1; k < hi; ++k) {
          if (_elem[k] < pivot) swap(_elem[++mi], _elem[k]);
      }
      swap(_elem[lo], _elem[mi]);
      return mi;
  }
  

  时间 / 空间复杂度 / 递归深度：最好$O(nlogn)$$O(nlogn)$，最坏$O(n)$$O(n)$

• 迭代 + 贪心 版本：

  xxxxxxxxxx
  #define Put(K, s, t) { if (1 < (t) - (s)) { K.push(s); K.push(t); } }
  #define Get(K, s, t) { t = K.pop(); s = K.pop(); }
  void quickSort(int lo, int hi) {
      Stack<int> Task;
      Put(Task, lo, hi);
      while (!Task.empty()) {
          Get(Task, lo, hi);
          int mi = partition(lo, hi);
          if (mi - lo < hi - mi) { Put(Task, mi + 1, hi); Put(Task, lo, mi); }
          else { Put(Task, lo, mi); Put(Task, mi + 1, hi); }
      }
  }
  

  空间复杂度：辅助栈空间不超过$O(logn)$$O(logn)$（递归深度可能超过）

统计序列逆序对

统计序列$A$$A$中逆序对的个数

xxxxxxxxxx
int mergeSort(int lo, int hi) {
    int count = 0;
    if (hi - lo < 2) return 0;
    int mi = (lo + hi) >> 1;
    count += mergeSort(lo, mi);
    count += mergeSort(mi, hi);
    count += merge(lo, mi, hi);
    return count;
}

int merge(int lo, int mi, int hi) {
    int cnt = 0;
    int i = 0; int* A = S + lo; 
    int j = 0, lb = mi - lo; int* B = new int[lb]; 
    for (int i = 0; i < lb; ++i) 
        B[i] = A[i]; 
    int k = 0, lc = hi - mi; int* C = S + mi; 
    
    while ((j < lb) && (k < lc)) {
        if (B[j] > C[k]) {
            cnt += (mi - lo - j); // count inversions
            A[i++] = C[k++];
        }
        else A[i++] = B[j++];
    }
    while (j < lb) 
        A[i++] = B[j++];
    delete [] B;
    return cnt;
}

时间复杂度：$O(nlogn)$$O(nlogn)$

最大间隙问题 MaxGap

给定$n$$n$个实数$x_1,x_2,...,x_n$$x_1, x_2, ..., x_n$，求这些数在实轴上相邻2个数之间的最大差值。

xxxxxxxxxx
int max(int n, double x[]) {
    int m = MIN_INT;
    for (int i = 0; i < n; i++)
        if (x[i] > x[m]) m = i;
    return m;
}

int min(int n, double x[]) {
    int m = MAX_INT;
    for (int i = 0; i < n; i++)
        if (x[i] < x[m]) m = i;
    return m;
}

double maxGap(int n, double x[]) {
    double maxx = x[max(n, x)];
    double minx = x[min(n, x)];
    int* cnt = new int[n];
    double* high = new double[n];
    double* low = new double[n];
    for (int i = 0; i < n; ++i) { // init
        cnt[i] = 0;
        high[i] = minx;
        low[i] = maxx;
    }
    for (int i = 0; i < n; ++i) {
        double avergap = (maxx - minx) / (n - 1);
        int index = (x[i] - minx) / avergap);
        if (index == n - 1) index = n - 2;
        cnt[index]++;
        if (x[i] > high[index]) high[index] = x[i];
        if (x[i] < low[index]) low[index] = x[i];
    }
    double ans = 0;
    double left = high[0];
    for (int i = 0; i < n; ++i) {
        if (cnt[i]) {
            double thisgap = low[i] - left;
            if (thisgap > ans) ans = thisgap;
            left = high[i];
        }
    }
    return ans;
}

时间复杂度：$O(n)$$O(n)$

进制转换

以10进制转16进制为例，自高而低输出结果

xxxxxxxxxx
void convert(Stack<char>& S, __int64 n, int base) {
    char digit[] = "0123456789ABCDEF"; 
    while (n > 0) {
        S.push( digit[n % base] );
        n /= base; 
    }
    while (!S.empty()) 
        printf("%c", S.pop());
}

时间复杂度：$O(n)$$O(n)$，$n$$n$为原整数位数

括号匹配

给定算式$x$$x$，判断算式中的括号是否匹配。设只存在一种括号。

xxxxxxxxxx
bool paren(const char x[], int lo, int hi) { //x[lo, hi)
    Stack<char> S;
    for (int i = lo; i < hi; ++i) {
        if ('(' == x[i]) S.push(x[i]);
        else if (!S.empty()) S.pop();
        else return false;
    }
    return S.empty();
}