排序算法

①冒泡排序:O()

int n;cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
        if(a[j-1]>a[j])swap(a[j-1],a[j]);

for(int i=1;i<=n;i++)cout<<a[i]<<' ';

②插入排序：O()

int  n;cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

int t;
for(int i=1;i<=n;i++){
    t=a[i];

    while(i&&a[i-1]>t){
        a[i]=a[i-1];i--;
    }
    a[i]=t;
}

for(int i=1;i<=n;i++)cout<<a[i]<<' ';

③选择排序：O()

int n;cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

for(int i=1;i<n;i++){
    int minn=i;

    for(int j=i+1;j<=n;j++){
        if(a[minn]>a[i])minn=j;

    swap(a[i],a[minn]);
}

for(int i=1;i<=n;i++)cout<<a[i]<<' ';

④桶排序

int n;cin>>n;

memset(num,0,sizeof(num));
for(int i=1;i<=n;i++){
    cin>>a[i];num[a[i]]++;
}

for(int i=1;i<=1000000;i++)
    if(num[i]!=0)
        for(int j=1;j<=num[i];j++)
            cout<<i<<' ';

⑤sort排序

//从小到大
bool cmp(int a,int b){return a<b;}
sort(a+1,a+n+1,cmp);
//从大到小
bool cmp(int a,int b){return a>b;}
sort(a+1,a+n+1,cmp);