目 录CONTENT

文章目录

acwing算法基础学习笔记

smallkun
2022-07-01 / 0 评论 / 0 点赞 / 256 阅读 / 839 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-07-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我删除。

算法基础

1.基础算法

排序

快速排序

  1. 确定分界点: q[l] q[(1+r)/2] q[r] 随机
  2. 调整区间:
    image-20220321191158800
  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. 逆序对的数量

排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定冒泡排序O(n2)O(n2)O(1)选择排序O(n2)O(n2)O(1)不是直接插入排序O(n2)O(n2)O(1)归并排序O(nlogn)O(nlogn)O(n)快速排序O(nlogn)O(n2)O(logn)不是堆排序O(nlogn)O(nlogn)O(1)不是希尔排序O(nlogn)O(n3)O(1)不是计数排序O(n+k)O(n+k)O(n+k)基数排序O(NM)O(NM)O(M)\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

树与图的遍历

最短路

最小生成树

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

0

评论区