排序問題(一維偏序)各種解法(選擇排序,冒泡排序,桶排序,sort排序,歸并排序)

• 前言
• 題目描述
  • 資料範圍
• 方法一:選擇排序/冒泡排序
• 方法二:桶排序(Barrel Sort)
• 方法三:sort排序
• 方法三:歸并排序

前言

最近學了偏序問題,什麼CDQ分治、樹套樹、CDQ套CDQ、CDQ加樹狀數組、CDQ加線段樹……到一邊去吧！~~

題目描述

給你一個數 n n ,接下來一行輸入nn個數a[i] ( 1≤i≤n 1 ≤ i ≤ n ),求它們從小到大的排序。

樣例輸入:

6

3 2 7 1 6 5

樣例輸出:

1 2 3 5 6 7

資料範圍

随接下來作者所講方法變化而變化~~~

方法一:選擇排序/冒泡排序

資料範圍: n≤5∗103 n ≤ 5 ∗ 10 3 ,每個數 0<a[i]≤109 0 < a [ i ] ≤ 10 9

時間均為 O(n2) O ( n 2 )

選擇排序原理:從小到大枚舉每個位置,然後從這個位置開始到最後中找數,每次确定一個位置上的數.

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

(Bubble Sort)

冒泡排序原理：它會周遊若幹次要排序的數列，每次周遊時，它都會從前往後依次的比較相鄰兩個數的大小；如果前者比後者大，則交換它們的位置。這樣，一次周遊之後，最小的元素就在數列的前面！ 采用相同的方法再次周遊時，第二小的元素就被排列在目前最小元素之後。

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

方法二:桶排序(Barrel Sort)

資料範圍: n≤107 n ≤ 10 7 ,每個數 0<a[i]≤107 0 < a [ i ] ≤ 10 7

将每個a[i]加入一個以值為下标的桶中,然後從最小到最大找一遍：

時間不穩定

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

方法三:sort排序

資料範圍:排序所能給出的最大範圍

調用algorithm庫下的sort排序函數

時間 O(nlogn) O ( n l o g n )

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

方法三:歸并排序

利用分治的思想把整個序列排序

時間 O(nlogn) O ( n l o g n )

#include<cstdio>
#include<algorithm>
#define MAXN 100000
using namespace std;
int n,a[MAXN+],tmp[MAXN+];
void Merge(int l,int m,int r){
    int p=l,q=m+,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)>>;
    MergeSort(l,mid);
    MergeSort(mid+,r);
    Merge(l,mid,r);
    return ;
}
int main(){
    n=read();
    for(int i=;i<=n;i++)
        scanf("%d",&a[i]);
    MergeSort(,n);
    printf("%d",a[]);
    for(int i=;i<=n;i++)
        printf(" %d",a[i]);
    printf("\n");
    return ;
}