P1177 【模板】排序

Flanksy · 2023-05-03 16:56:05 · 题解

简单排序 & 分块优化

有动图，建议在博客内阅读

前言

意义不大的感叹。

这篇文章主要介绍选择排序和应用分块优化时间复杂度的方法，分块优化对插入排序、冒泡排序等同样适用。 结尾顺带写了插入排序和冒泡排序。

文章中 n 表示待排序元素数量，和题目中意义相同。

选择排序

一种比较暴力的排序方法，将序列分为有序区和无序区，开始时有序区没有元素，每次找到无序区中最小的元素放入有序区，当无序区没有元素时排序结束。

每次找到的无序区最小的元素都将成为有序区最大的元素，由于是从小到大排序，把元素放在有序区右边即可，图示：

橙色区域为有序区，蓝色区域为无序区，红色元素为无序区当前的最小元素。

选择排序的过程如下：

遍历无序区，标记最小元素的位置。
交换无序区第一个元素和最小元素。
标记无序区的第一个元素为有序的。
如果无序区为空，排序结束。

有序区和无序区仅用来帮助理解，代码实现中不需要标记。

简单来说就是在第 i 轮找到第 i 大的元素放到有序区第 i 个位置。

每次遍历无序区都会向有序区添加一个元素，一共遍历 n 次，每次遍历到的元素数量虽然递减，但仍然和 n 同阶。

时间复杂度 O(n^2)，适用于 n\leq 20000 的情况。

#include<algorithm>
#include<iostream>
using namespace std;
int n,a[100001];
void selection_sort(int l,int r){//对区间[l,r]排序
    int length=r-l+1;//区间长度即为遍历无序区的次数,每轮无序区即[l+i-1,r]
    for(int i=1;i<=length;i++){
        int aim=l+i-1;//最小元素的初始位置可以在无序区任取,这里选择无序区第一个元素
        for(int j=l+i-1;j<=r;j++) if(a[j]<a[aim]) aim=j;
        swap(a[l+i-1],a[aim]);//交换无序区第一个元素和最小元素
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    selection_sort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

分块优化

本题中 n\leq 100000，选择排序等时间复杂度为 O(n^2) 的排序算法一般无法通过，这时可以考虑分块以优化时间复杂度。

分块即将序列分成几个部分，分别处理然后合并来得到最终答案。

分块的技巧极多，笔者不能全部解释明白，这里默认块长为 \sqrt n（向下取整），详细解释写在后文的补充中，感兴趣的读者可以自行查看后面的内容。

由于块长已经设定为 \sqrt n，序列将会被分成约 n\div \sqrt n=\sqrt n 块（n 不一定为完全平方数），对这 \sqrt n 个块分别进行选择排序。对一个块排序的时间复杂度为 O(\sqrt n^2)，一共 \sqrt n 个块。

时间复杂度 O(\sqrt n^2 \times \sqrt n)=O(n\sqrt n)。

现在序列是局部有序的，接下来该合并答案了，但是不知道如何合并。如果再对整体进行选择排序，时间复杂度还是 O(n^2)，不可接受。感觉需要利用一些性质，先将序列的特殊性质罗列出来：

局部有序。

只有一个选项，答案不言而喻：整个序列中最小的元素一定是某个块的第一个元素。 每次遍历所有块的首个元素，其中最小的元素即为当前序列最小的元素。

每次遍历 \sqrt n 个块，一共遍历 n 次，时间复杂度 O(n\sqrt n)。

分块优化后的选择排序过程如下：

预处理：
- 将序列分成长度至多 \sqrt n 的 \sqrt n 块，注意最后一块可能并没有 \sqrt n 个元素。
- 记录每个块的块首、块尾位置，对每个块进行选择排序。
合并块：
- 遍历所有块，找到当前序列最小的元素，记录其所属块的编号。
- 将当前最小的元素加入最终有序序列，这个元素所属块的块首前移。

如果某个块的块首超出了块尾，说明这个块是空的，跳过它即可。

总体时间复杂度 O(n\sqrt n)，适用于 n\leq 500000 的情况。

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,block_len,block_num,head[1001],tail[1001],a[100001],ans[100001];
void selection_sort(int l,int r){
    int length=r-l+1;
    for(int i=1;i<=length;i++){
        int aim=l+i-1;
        for(int j=l+i-1;j<=r;j++) if(a[j]<a[aim]) aim=j;
        swap(a[l+i-1],a[aim]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    block_len=sqrt(n);//计算块长 
    block_num=(n-1)/block_len+1;//除法上取整计算块数,也可以换用下面一行统计块数 
//  for(int i=0;i<=n-1;i+=block_len) block_num++;

    for(int i=1;i<=block_num-1;i++){//最后一块可能不完整,单独处理 
        head[i]=block_len*(i-1)+1;//块i包含的范围是[head[i],tail[i]] 
        tail[i]=head[i]+block_len-1;
    }
    head[block_num]=block_len*(block_num-1)+1;
    tail[block_num]=n;
    for(int i=1;i<=block_num;i++) selection_sort(head[i],tail[i]);

    for(int i=1;i<=n;i++){
        int aim=0;//aim:块首元素最小的块编号 
        for(int j=1;j<=block_num;j++)
            if(head[j]<=tail[j]){aim=j;break;}//找一个非空块的块首 

        for(int j=aim+1;j<=block_num;j++){
            if(head[j]>tail[j]) continue;
            if(a[head[j]]<a[head[aim]]) aim=j;
        }
        ans[i]=a[head[aim]];//计入答案 
        head[aim]++;//块首前移 
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

关于块长

块长可以设为常数，一般情况下块长只要和 \sqrt n 同阶就没有问题，n 需要取上界 10^5。笔者的实现中选择 \sqrt n 作块长，这里（并不严谨地）解释原因。

设块长为 x，块数量就为 y=n/x。

预处理时间复杂度 O(x^2y)=O(x^2 \times n / x)=O(nx)，合并块时间复杂度 O(ny)=O(n\times n / x)=O(n^2/x)。

利用基本不等式可知当 x=\sqrt n 时 nx 和 n^2/x 中的最大值最小且 nx+n^2/x 取最小值。

完整代码：本题数据范围下块长固定在 1000 左右时效率最高。

经过测试优秀的实现可以在 1s 内完成 10^6 个元素的排序。

插入排序

将序列分成有序区和无序区，每次随便从无序区找一个元素（一般取第一个元素）插入到有序区，插入时操作有序区来保持其有序性质，图示：

常数较小，一般比选择排序和冒泡排序都快。

插入排序的过程如下：

在无序区选中一个元素。
有序区向右扩展，所有比该元素大的元素右移，创造一个空位。
将选中的元素放入空位。
如果无序区为空，排序结束。

进行 n 次插入，有序区每轮最坏移动次数与 n 同阶，时间复杂度 O(n^2)。

代码仅给出函数部分。

void insection_sort(int l,int r){//对区间[l,r]排序 
    int length=r-l+1;
    for(int i=1;i<=length;i++){
        int pos=l+i-2,now=a[l+i-1];//无序区第一个元素会被覆盖 
        while(pos>=l&&a[pos]>now) a[pos+1]=a[pos],pos--;
        a[pos+1]=now;//注意pos+1才是空位 
    }
}

冒泡排序

在冒泡排序中，一般无序区在有序区左边，即一般先找出较大值。

遍历无序区，如果某个元素比其右边的元素大就交换，图示：

每轮会将无序区的最大元素换到最右边。如同泡泡从水中上浮，体积最大的会先浮出水面。

冒泡排序的过程如下：

遍历无序区，如果某个元素比其右边的元素大就交换它们。
标记无序区最右端的元素为有序。
如果无序区为空，排序结束。

进行 n 轮，每轮遍历的元素数量与 n 同阶，时间复杂度 O(n^2)。

代码仅给出函数部分。

void bubble_sort(int l,int r){
    int length=r-l+1;
    for(int i=1;i<=length;i++)//注意a[r]不应与其右边元素比较
        for(int j=l;j<=r-i;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}

后记

这个算法是我独立想出来的，以前不会分块但是一直挺好奇，有一天突发奇想“排序能不能分块”，仔细想想感觉对每个块暴力时间复杂度挺对，又想了想发现可以像归并一样合并，时间复杂度也很对。于是就有了这篇文章里的内容，笔者第一次写分块就是这个排序算法。后来发现数据结构题的分块实现和排序还是挺不一样的。

上边的分块优化代码里选择排序换成文中其他两个也能通过。

朴素的选择排序、插入排序、冒泡排序都交了一遍，选择排序过了三个测试点，另外两个过了一个测试点。分块 + 插入排序最快，毕竟插入排序最好时间复杂度是 O(n) 嘛。不过冒泡排序也能做到最好时间复杂度 O(n)。

希望我的学弟学妹们会比我更强。

P1177 【模板】 排序