P1177 【模板】排序题解

Lovely_Chtholly · 2023-05-04 13:51:22 · 题解

题目传送门

【分析】

可以用 STL 中的 sort 过，但是这里会多介绍几种方法,这里主要讲 STL sort 和归并排序。

【各种基础排序】

STL sort

这个函数是 STL 中的快排，需要调用头文件 #include<algorithm>，用 sort(a+1,a+1+n) 可以实现从 a_1 到 a_n 的排序，默认顺序为从小到大，若想从大到小排序，可以自己写 cmp 函数，也可以用 greater<int>()。

cmp 函数使用方法：

bool cmp(int n,int m)
{
    return n>m;
}
sort(a+1,a+1+n,cmp);

greater<int>() 使用方法：

sort(a+1,a+1+n,greater<int>());

【AC 代码】

#include<bits/stdc++.h>//这里我用了万能头，就没用 #include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
inline int read()
{
    char ch=getchar();
    int n=0,m=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')m=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
    return n*m;
}
void write(int n)
{
    if(n>9)write(n/10);
    putchar(n%10+'0');
}
int n,a[N];
int main(int argc,char **argv)
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+1+n);//这题要从小到大排序，所以不用写 cmp 函数和 greater<int>()
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

归并排序

原理：运用二分，将一个序列分成多个小序列进行排序，最后再合并。

流程：

递归分治左右。
设置两个指针分别指向两个子数组开头。
开始合并。
哪一边先空了就直接把另一边复制过去。
两个子数组中哪个数字小就复制哪一个，然后对应的指针自增。
将两个序列合并至一个。

举个例子（学校上传不了图片有点难看）：

[9 8 7 6 5 4 3 2 1]

可以分成两段：

[9 8 7 6 5] [4 3 2 1]

继续分：

[9 8] [7] [6] [5] [4] [3] [2] [1]

[9] [8] [7] [6] [5] [4] [3] [2] [1]

合并：

[8 9] [7] [6] [5] [4] [3] [2] [1]

[7 8 9] [5 6] [3 4] [1 2]

[5 6 7 8 9] [1 2 3 4]

[1 2 3 4 5 6 7 8 9]

代码：

void merge(int a[],int l,int mid,int r)
{
    int b[r-l+1];
    for(int i=l;i<=r;i++)b[i-l]=a[i];
    int i=l,j=mid+1;
    for(int k=l;k<=r;k++)
    {
        if(i>mid)a[k]=b[j-l],j++;
        else if(j>r)a[k]=b[i-l],i++;
        else if(b[i-l]<b[j-l])a[k]=b[i-l],i++;
        else a[k]=b[j-l],j++;
    }
}
//归并排序，参数：数组名，左右区间
void merge_sort(int a[],int l,int r)
{
    //递归出口，当划分到只有一个元素时，停止递归
    if(l>=r)return;
    int mid=(l+r)/2;
    merge_sort(a,l,mid),merge_sort(a,mid+1,r),merge(a,l,mid,r);
}

插入排序

原理：将一个元素插入到已排好序的序列中，使序列仍然有序。

void Insert_Sort()
{
    int k=0,j=0;
    for(int i=1;i<10;i++)
    {
        k=a[i],j=i-1;
        while(j>=0 and k<a[j])a[j+1]=a[j],j--;//找到位置以后后移
        a[j+1]=k;
    }
}

快速排序

原理：确定一个基准数，把要排序的序列以基准数为界分成两部分分别排序。

流程：

设置基准数，把序列分成两部分。
找第一个小于基准数的数和第一个大于基准数的数。
如果第一个大于基准数的数的下标比第一个小于基准数的数的下标小，那么交换他们。
将基准数归位。
递归对左右两边进行排序。

代码：

void quickSort(int a[],int l,int r)
{
    if(l>r)return;
    int i=l,j=r;
    int tmp=a[l];
    while(i!=j)
    {
        while(a[j]>=tmp and i<j)j--;
        while(a[i]<=tmp and i<j)i++;
        if(i<j)swap(a[i],a[j]);
    }
    swap(a[l],a[i]),quickSort(a,l,i-1),quickSort(a,i+1,r);
}

选择排序

原理：从待排序的元素中选出最小（或最大）的一个元素，放到序列的起始位置，然后再从剩余的未排序元素中寻找到最小（或最大）的元素放到已排序的序列的末尾。以此类推，直到待排序的元素个数为零。

for(int i=1;i<=n;i++)
{
    minn=INF;
    for(int j=i;j<=n;j++) //j从第i个位置开始找最小的
        if(minn>a[j])minn=a[j],k=j;
    //交换
    swap(a[i],a[k]);
}

【其他更高级的排序】

基数排序

原理：对于待排序的数据，整体权重未知的情况下，先按权重小的因子排序，然后按权重大的因子排序。

int getDigitNum(int x)
{
    if(!x)return 1;
    int sum=0;
    while(x)sum++,x/=10;
    return sum;
}
void RadixSort()
{
    int maxx=a[0];
    for(int i=1;i<n;i++)maxx=max(maxx,a[i]);
    //确定最大的位数
    int maxn=getDigitNum(maxx),x=1;
    for(int k=0;k<maxn;k++)
    {
        vector<int>v[10];
        for(int i=0;i<10;i++)v[i].clear();
        for(int i=0;i<n;i++)
        {
            int tmp=a[i]/x%10;
            v[tmp].push_back(a[i]);
        }
        int cnt=0;
        for(int i=0;i<10;i++)
            for(int j=0;j<v[i].size();j++)a[cnt++]=v[i][j];
        x*=10;
    }
}

希尔排序

原理：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

void shell_sort()
{
    int j;
    for(int k=n/2;k>0;k/=2)
        for(int i=k;i<n;i++)
        {
            int tmp=a[i];
            for(j=i-k;j>=0 and tmp<a[j];j-=k)a[j+k]=a[j];
            a[j+k]=tmp;
        }
}

ps：我没用其他排序 AC 这道题，所以只有 STL sort 有完整代码

P1177 【模板】排序 题解

【分析】

【各种基础排序】

【其他更高级的排序】

P1177 【模板】排序题解