算法基础

1.基础算法

排序

快速排序

1. 确定分界点: q[l] q[(1+r)/2] q[r] 随机
2. 调整区间:
   
3. 递归处理左右两段

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

AcWing 785. 快速排序

AcWing 786. 第k个数

归并

1. 确定分界点:mid = (1+r)/2
2. 递归排序left right
3. 归并——合二为一

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

AcWing 787. 归并排序

AcWing 788. 逆序对的数量

$$\begin{array}{|c|c|c|c|c|} \hline {排序算法} & {平均时间复杂度} & {最坏时间复杂度} & {空间复杂度} & {是否稳定} \\ \hline {冒泡排序} & {O(n^2)} & {O(n^2)} & {O(1)} & {是} \\ \hline {选择排序} & {O(n^2)} & {O(n^2)} & {O(1)} & {不是} \\ \hline {直接插入排序} & {O(n^2)} & {O(n^2)} & {O(1)} & {是} \\ \hline {归并排序} & {O(nlogn)} & {O(nlogn)} & {O(n)} & {是} \\ \hline {快速排序} & {O(nlogn)} & {O(n^2)} & {O(logn)} & {不是} \\ \hline {堆排序} & {O(nlogn)} & {O(nlogn)} & {O(1)} & {不是} \\ \hline {希尔排序} & {O(nlogn)} & {O(n^3)} & {O(1)} & {不是} \\ \hline {计数排序} & {O(n+k)} & {O(n+k)} & {O(n+k)} & {是} \\ \hline {基数排序} & {O(N*M)} & {O(N*M)} & {O(M)} & {是} \\ \hline \end{array}$$

二分

高精度

前缀和差分

双指针算法

位运算

离散化

区间合并

2.数据结构

链表与邻接表：树与图的存储

栈与队列：单调队列、单调栈

KMP

Trie

并查集

堆

Hash表

3.搜索与图论

DFC与BFS

树与图的遍历

最短路

最小生成树

二分图：染色法、匈牙利算法