今天学习了素数筛和排序的几种方法，emmmm因为非常容易忘掉于是就写下来总结一下！

普通筛法

从2开始，把所有的数的倍数都标记为合数，剩下的就是素数，复杂度大概是O(nlogn) 似乎还行emmmmm，code:

1
2
3
4
5
6
7
8
9
10
11
bool vis[200001];
int Prime[2000001];
int n,ans;
for(int i=2;i<n;i++)
{
    if(!vis[i]) Prime[++ans]=i;
    for(int j=2;j*i<=n;j++)
    vis[i*j]=true;
}
for(int i=1;i<=ans;i++)
cout<<Prime[i]<<endl;

欧拉筛

普通的筛法速度还不够快，嗯，难道你没有发现有很多重复的计算步骤嘛，比如24就足足被2、3、4、6、8、12一共筛了六次，那么我们怎么才能让24只被筛一次呢?

24被筛两次是因为它有多个因子，所以每个因子在筛自己的倍数的时候都会筛掉24，我们只要24的一个因子筛掉它就好了，那么谁筛掉它呢，自然是24的最大因子或者最小因子啦。其实两个是一样的，因为知道最大因子也就知道了最小因子嘛。

众所周知，一个非一的正整数数可以被分解为若干个素数的乘积，比如24=2*2*2*3，那么我们就让24只被2或者2*2*3=12筛掉不就好了。欧拉筛的算法就是枚举最大因子（从2到n），然后乘上一个最小质因子，来筛掉对应的合数。因为最小质因子一定是一个素数并且是合数分解后最小的素数，所以就可以在素数数组Prime里面从小到大枚举最小质因子，然后把乘起来的数筛掉，一旦不符合最小，那就结束循环。这样可以保证被筛掉的数只由最大因数筛掉（也就是枚举的i），最大质因数能筛掉几个数数取决于有多少个质数符合最小质因数（也就是枚举Prime数组，直到不符合最小），代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool vis[200001];
int Prime[200001];
int n,ans;
for(int i=2;i<=n;i++)
{
    if(!vis[i]) Prime[++ans]=i; //如果没有被筛掉，那么就是素数啦
    for(int j=1;j<=ans&&i*Prime[j]<=n;j++)
    {
        vis[i*Prime[j]]=true; //筛掉每一个符合要求的合数，i是最大因子，Prime[j]是最小质因子
        if(!i%Prime[j]) break;//如果再大就无法保证最小质因子了
    }
}
for(int i=1;i<=ans;i++)
cout<<Prime[i]<<endl;

快速排序

快速排序的思想就是分治思想，它先从一组数里面选一个数作为比较对象，然后将所有大于等于它的放在它后面，所有小于等于它的放在它前面。然后对它前面或者后面的数视为新的一组数，重复上述操作，不断的分割，越分越小，直到最后全部元素有序。代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void Sort(int Left,int Right)
{
    int x=Left,y=Right; //记录原范围
    int Mid=a[(Left+Right)/2]; //选取一个中间的数作为比较对象
    while(Left<=Right) //小于等于 保证最终退出循环的时候Left>Right
    {
        while(a[Left]<Mid) Left++; //比较对象也需要被移动所以没有=
        while(a[Right]>Mid) Right--; //同理
        if(Left<=Right) swap(a[Left++],a[Right--]); //交换 相等也交换，使Left>Right
    }
    if(Left<y) Sort(Left,y); //分治
    if(Right>x) Sort(x,Right);
}

上面的代码思维和传统的快速排序有些不同，上面是凑成两个需要移动的数之后交换位置，这样节省运算。注意思考里面的比较符号，为什么有的有等号，有的没有。尤其是两个 Left<=Right 的判断使得在退出循环时 Left>Right 并且在往下分治的时候中间不会有遗漏的数字没有被分走。上述代码只能保证一个比较对象处于正确的位置，如果有多个值和比较对象相同的元素，其他基本上随机分布。但这并不影响程序的正确，只会降低运行速度。

归并排序

非常稳定，详情请在本站搜索归并排序。

插入排序

将数组里面的元素一次插入一个空数组里面，保证新数组里面的元素一直是单调的，这样每次插入可以用二分，一共插入n次就排好序了。缺点是不稳定，每次插入新元素后面的元素就要移位置，会花时间。