洛谷 P1177 【模板】快速排序 冒泡排序快速排序归并排序STL中sort函数

洛谷 P1177 【模板】快速排序   冒泡排序/快速排序/归并排序/STL中sort函数

在线测评地址https://www.luogu.org/problem/P1177

四种方法

方法一：冒泡排序

#include <stdio.h> #define maxn 100100 int a[maxn]; int main(){ int i,n,j,t; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) if(a[i]>a[j])t=a[i],a[i]=a[j],a[j]=t; for(i=1;i<=n;i++)printf("%d ",a[i]); return 0; }

方法二：快速排序

 

#include <stdio.h> #define maxn 100100 int a[maxn],n; void qsort(int left,int right){ int i=left,j=right,mid=a[(left+right)/2],t; while(i<=j){ while(a[i]<mid)i++; while(mid<a[j])j--; if(i<=j){ t=a[i],a[i]=a[j],a[j]=t,i++,j--; } } if(left<j)qsort(left,j); if(i<right)qsort(i,right); } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); qsort(1,n); for(i=1;i<=n;i++)printf("%d ",a[i]); return 0; }

方法三：归并排序

#include <stdio.h> #define maxn 100100 int a[maxn],n,b[maxn]; void memory_sort(int s1,int e1,int s2,int e2){ int i=s1,j=s2,k=s1; while(i<=e1&&j<=e2){ if(a[i]<a[j])b[k++]=a[i++]; else b[k++]=a[j++]; } while(i<=e1)b[k++]=a[i++]; while(j<=e2)b[k++]=a[j++]; for(i=s1;i<=e2;i++)a[i]=b[i]; } void merge_sort(int left,int right){ int mid=(left+right)/2; if(left>=right)return; merge_sort(left,mid); merge_sort(mid+1,right); memory_sort(left,mid,mid+1,right); } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); merge_sort(1,n); for(i=1;i<=n;i++)printf("%d ",a[i]); return 0; }

方法四：STL中sort函数

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