https://visualgo.net/zh/sorting 算法可视化

查找

1、二分查找

元素必须是有序的，如果是无序的则要先进行排序操作。最坏情况下，关键词比较次数为 l o g 2 n + 1 且期望时间复杂度为l o g 2 n

2、插值查找

![alt](https://uploadfiles.nowcoder.com/images/20220227/937512194_1645934928462/D2B5CA33BD970F64A6301FA75AE2EB22)

按比例查找：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)//按照数据在首尾数据间的比例查找

排序

1.希尔排序（组内插入排序）

        int d  = a.length;
        while (d!=0) {
            d=d/2;
            for (int x = 0; x < d; x++) {//分的组数
                for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
                    int j = i - d;//j为有序序列最后一位的位数
                    int temp = a[i];//要插入的元素
                    while(j >= 0 && temp < (a[j -= d])) {//从后往前遍历。
                        a[j + d] = a[j];//向后移动d位
                    }
                    a[j + d] = temp;
                }
            }
        }
    }

2.简单选择排序

第一次选择一个最小的数，放在第一个，然后一直循环做n次。

3.堆排序

堆中某个节点的值总是不大于（或不小于）其父节点的值(左右子树谁大谁小并没有规定，左子树可以比右子树大)。
插入、删除、建堆都是l o g 2 n 
最坏情况可能是O(n)

//1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

2、从堆顶中取出元素
	swap(arr,0,j);//将堆顶元素与末尾元素进行交换
    adjustHeap(arr,0,j);//重新对堆进行调整
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
 
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

4.快排排序

       public void quickSort(int[] arr, int l, int r){
        if(l < r){
            int temp = arr[l];
            int i = l;
            int j = r;
            while(l <= r){
                while(arr[i] <= temp && i < j ){
                    i++;
                }
                while(arr[j] > temp && i < j){
                    j--;
                }
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
            arr[i] = temp;
            quickSort(arr,l,i -1);
            quickSort(arr, i + 1, r);
        }
   
最好：O(n l o g 2 n )
最坏：O ( n 2 ） (接近有序的时候)
空间复杂度：o（nlog2n）
稳定性：不稳定

5.归并排序

#include<iostream>
using namespace std;

void Merge(int arr[],int low,int mid,int high){
   //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
   int i=low,j=mid+1,k=0; //mid+1为第2有序区第1个元素，j指向第1个元素
   int *temp=new(nothrow) int[high-low+1]; //temp数组暂存合并的有序序列
   if(!temp){ //内存分配失败
       cout<<"error";
       return;
   }
   while(i<=mid&&j<=high){
       if(arr[i]<=arr[j]) //较小的先存入temp中
           temp[k++]=arr[i++];
       else
           temp[k++]=arr[j++];
   }
   while(i<=mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
       temp[k++]=arr[i++];
   while(j<=high)//同上
       temp[k++]=arr[j++];
   for(i=low,k=0;i<=high;i++,k++)//将排好序的存回arr中low到high这区间
   	arr[i]=temp[k];
   delete []temp;//删除指针，由于指向的是数组，必须用delete []
}

//用递归应用二路归并函数实现排序——分治法
void MergeSort(int arr[],int low,int high){
   if(low<high){
       int mid=(low+high)/2;
       MergeSort(arr,low,mid);
       MergeSort(arr,mid+1,high);
       Merge(arr,low,mid,high);
   }
}
平均时间复杂度：O(nlogn)
最佳时间复杂度：O(n)
最差时间复杂度：O(nlogn)
空间复杂度：O(n)
归并排序比较占用内存，但效率高且稳定。

6.基数排序

用于大量数，很长的数进行排序时。

1将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
2将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列

图论

图的存储方式，广度搜索和深度搜索

邻接矩阵：本质就是2*2的数组

邻接表：数组+列表，和哈希表的存储方式差不多

深度搜索（dfs）：可以使用递归或者栈来实现

广度搜索（bfs）：使用列表实现

最短距离

Dijkstra最短路径算法（求一个点到其他点的最短距离）

Floyd算法（求各个点的最短距离）本质就是动态规划，

公式：顶点i 到顶点j 的新距离 = Min（顶点i 到顶点j 的旧距离，顶点i 到顶点n 的距离+顶点n 到顶点j 的距离）

最小生成树

prim算法（贪心算法）：

任意点为起点，将边加入点集合中。

复杂度：O（v2）

karsual

边排序，从小到大构建。 O(ElogE)

并查集

主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。

查询（Find）：查询两个元素是否在同一个集合中。

性能跟树的深度有关系，并查集的时间复杂度为 O(logn)

拓扑排序

// deg是入度，在存图的时候需要录入数据
// A是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort(int n)
{
   int cnt = 0;
   queue<int> q;
   for (int i = 1; i <= n; ++i)
       if (deg[i] == 0)
           q.push(i);
   while (!q.empty())
   {
       int t = q.front();
       q.pop();
       A[cnt++] = t;
       for (auto to : edges[t])
       {
           deg[to]--;
           if (deg[to] == 0) // 出现了新的入度为0的点
               q.push(to);
       }
   }
   return cnt == n;
}
``
##海量数据去重

需要从海量数据中查询某字符串是否存在

![alt](https://uploadfiles.nowcoder.com/images/20220228/937512194_1646015808335/D2B5CA33BD970F64A6301FA75AE2EB22)
缓存穿透：server端请求数据时，server缓存db，redis和mysql都不存在数据。
server请求数据过程：
1先访问redis，如果存在，直接返回，
2不存在则访问mysql，
3mysql如果不存在，返回，
4如果存在，将mysql存在的key写回redis

解决缓存穿透：
   1.在redis端设置<key,null>键值对，以此避免访问mysql；
   	缺点：<key,null>过多，占用内存
   *可以给key设计过期expire key 600ms，停止攻击后最终由redis自动清除无用的key；
   方法2：在**server端**存储一个布隆过滤器，将mysql包含的key放入布隆过滤器中，布隆过滤器能过滤一定不存在的数据
   
   
###布隆过滤器

八股文——数据结构

查找