排序问题(一维偏序)各种解法(选择排序,冒泡排序,桶排序,sort排序,归并排序)

• 前言
• 题目描述
• 方法一:选择排序/冒泡排序
• 方法二:桶排序(Barrel Sort)
• 方法三:sort排序
• 方法三:归并排序

前言

最近学了偏序问题,什么CDQ分治、树套树、CDQ套CDQ、CDQ加树状数组、CDQ加线段树……到一边去吧！~~

题目描述

给你一个数n$n$,接下来一行输入n$n$个数a[i] (1≤i≤n$1\le i\le n$),求它们从小到大的排序。
样例输入:
6
3 2 7 1 6 5
样例输出:
1 2 3 5 6 7

数据范围

随接下来作者所讲方法变化而变化~~~

方法一:选择排序/冒泡排序

数据范围:n≤5∗103$n\le 5\ast {10}^3$,每个数0<a[i]≤109$0<a[i]\le {10}^9$
时间均为O(n2)$O(n^2)$
选择排序原理:从小到大枚举每个位置,然后从这个位置开始到最后中找数,每次确定一个位置上的数.

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 5000
int a[MAXN+5];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]>a[j])//交换位置
                swap(a[i],a[j]);
    printf("%d",a[1]);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i]);
    printf("\n");
    return 0;
}

(Bubble Sort)
冒泡排序原理：它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最小的元素就在数列的前面！ 采用相同的方法再次遍历时，第二小的元素就被排列在当前最小元素之后。

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 5000
int a[MAXN+5];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[j]>a[j+1])//交换位置
                swap(a[j],a[j+1]);
    printf("%d",a[1]);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i]);
    printf("\n");
    return 0;
}

方法二:桶排序(Barrel Sort)

数据范围:n≤107$n\le {10}^7$,每个数0<a[i]≤107$0<a[i]\le {10}^7$
将每个a[i]加入一个以值为下标的桶中,然后从最小到最大找一遍：
时间不稳定

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10000000
#define INF 0x3f3f3f3f
int a[MAXN+5];
bool Barrel[MAXN+5];
int main(){
    int Min=INF,Max=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]),Barrel[a[i]]=1;
        Min=min(Min,a[i]);
        Max=max(Max,a[i]);
    }
    int flag=0;
    for(int i=Min;i<=Max;i++)
        if(Barrel[i]){
            if(!flag) flag++,printf("%d",i);
            else printf(" %d",i);
        }
    printf("\n");
    return 0;
}

方法三:sort排序

数据范围:排序所能给出的最大范围
调用algorithm库下的sort排序函数
时间O(nlogn)$O(nlo{g}_n)$

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1000000
#define INF 0x3f3f3f3f
int a[MAXN+5];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    printf("%d",a[1]);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i]);
    printf("\n");
    return 0;
}

方法三:归并排序

利用分治的思想把整个序列排序
时间O(nlogn)$O(nlo{g}_n)$

#include<cstdio>
#include<algorithm>
#define MAXN 100000
using namespace std;
int n,a[MAXN+5],tmp[MAXN+5];
void Merge(int l,int m,int r){
    int p=l,q=m+1,len=l;
    while(p<=m&&q<=r){
        if(a[p]<=a[q]) tmp[len++]=a[p++];
        else tmp[len++]=a[q++];
    }
    while(p<=m) tmp[len++]=a[p++];
    while(q<=r) tmp[len++]=a[q++];
    for(int i=l;i<=r;i++)
        a[i]=tmp[i];
    return ;
}
void MergeSort(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    MergeSort(l,mid);
    MergeSort(mid+1,r);
    Merge(l,mid,r);
    return ;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    MergeSort(1,n);
    printf("%d",a[1]);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i]);
    printf("\n");
    return 0;
}