- 前言
- 題目描述
- 資料範圍
- 方法一:選擇排序/冒泡排序
- 方法二:桶排序(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 ;
}