各种排序

给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果。本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下:
数据1:只有1个元素;
数据2:11个不相同的整数,测试基本正确性;
数据3:103个随机整数;
数据4:104个随机整数;
数据5:105个随机整数;
数据6:105个顺序整数;
数据7:105个逆序整数;
数据8:105个基本有序的整数;
数据9:105个随机正整数,每个数字不超过1000。

输入格式

输入第一行给出正整数N105N(≤10^5),随后一行给出N个(长整型范围内的)整数,其间以空格分隔。

输出格式

在一行中输出从小到大排序后的结果,数字间以1个空格分隔,行末不得有多余空格。

输入样例

11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例

-20 -17 -5 0 4 8 10 29 43 50 981
#include<iostream>
#define maxnum 10050
using namespace std;
int n;
long a[maxnum];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    mysort(0,n-1);
    for(int i=0;i<n-1;i++)cout<<a[i]<<' ';
    cout<<a[n-1];
}
//冒泡排序
void mysort(int start,int end){                 
    for(int i=end-start;i>0;i--){
        int flag=0;
        for(int j=0;j<i;j++){
            long tmp=a[j];
            if(a[j]>a[j+1]){
                a[j]=a[j+1],a[j+1]=tmp;
                flag=1;
            }
        }
        if(!flag)break;
    }
}
//插入排序
void mysort(int start,int end){
    for(int i=1;i<=end-start;i++){
        int j;
        long tmp=a[i];
        for(j=i;j>0&&a[j-1]>tmp;j--)a[j]=a[j-1];
        a[j]=tmp;
    }
}
//希尔排序
void mysort(int start,int end){      //希尔排序:基于原始增量序列版本
    for(int length=(end+start)/2;length>0;length/=2){
        for(int i=1;i<n;i++){
            int j;
            long tmp=a[i];
            for(j=i;j>=length&&a[j-length]>tmp;j-=length)a[j]=a[j-length];
            a[j]=tmp;
        }
    }
}
void mysort(int start,int end){      //希尔排序:基于Sedgewick增量序列版本
    int Sedgewick[]={929,505,209,109,41,19,5,1,0};
    for(int l=0;Sedgewick[l]>end-start;length=Sedgewick[l++]);
    for(int length=Sedgewick[l];length>0;l++){
        for(int i=1;i<n;i++){
            int j;
            long tmp=a[i];
            for(j=i;j>=length&&a[j-length]>tmp;j-=length)a[j]=a[j-length];
            a[j]=tmp;
        }
    }
}
//堆排序
void percdown(int root,int size){
    long tmp=a[root];
    int parent,child;
    for(parent=root;parent*2+1<size;parent=child){
        child=parent*2+1;
        if(child<size-1&&a[child]<a[child+1])child++;
        if(tmp>=a[child])break;
        else a[parent]=a[child];
    }
    a[parent]=tmp;
}
void mysort(int start,int end){
    for(int i=(end-start+1)/2;i>=0;i--)percdown(i,end-start+1);
    for(int i=end-start;i>0;i--){
        long tmp=a[0];
        a[0]=a[i],a[i]=tmp;
        percdown(0,i);
    }
}
//归并排序
long tmpa[maxnum];
void merge(long*a,long*tmpa,int start,int end,int center){ //归并子列
    int start1=start,end1=center,start2=center+1,end2=end,tmp=start;
    while(start1<=end1&&start2<=end2){
        if(a[start1]<=a[start2])tmpa[tmp++]=a[start1++];
        else tmpa[tmp++]=a[start2++];
    }
    while(start1<=end1)tmpa[tmp++]=a[start1++];
    while(start2<=end2)tmpa[tmp++]=a[start2++];
    for(int i=start;i<=end;i++)a[i]=tmpa[i];
}
void mysort(int start,int end){     //归并排序:递归版本
    if(start>=end)return;
    int center=(start+end)/2;
    mysort(start,center);
    mysort(center+1,end);
    merge(a,tmpa,start,end,center);
}
void mysort(int start,int end){     //归并排序:非递归版本
    int length=1;
    while(length<=end-start){
        int i;
        for(i=0;i<=n-length*2;i+=length*2)merge(a,tmpa,i,i+length*2-1,i+length-1);
        if(i+length<=n)merge(a,tmpa,i,n-1,i+length-1);
        else for(int j=i;j<n;j++)tmpa[j]=a[j];
        length*=2;
        for(i=0;i<=n-length*2;i+=length*2)merge(tmpa,a,i,i+length*2-1,i+length-1);
        if(i+length<=n)merge(tmpa,a,i,n-1,i+length-1);
        else for(int j=i;j<n;j++)a[j]=tmpa[j];
        length*=2;
    }
} 
//快速排序
int compare(const void*num1,const void*num2){
    return (*(int*)num1-*(int*)num2);
}
void mysort(int start,int end){                 //快速排序:库函数版本
    qsort(a,end-start+1,sizeof(long),compare);
}
int cutoff;
void swap(long*element1,long*element2){
    long tmp=*element1;
    *element1=*element2,*element2=tmp;
}
long median(int start,int end){
    int center=(start+end)/2;
    if(a[start]>a[center])swap(&a[start],&a[center]);
    if(a[start]>a[end])swap(&a[start],&a[end]);
    if(a[center]>a[end])swap(&a[center],&a[end]);
    swap(&a[center],&a[end-1]);
    return a[end-1];
}
void mysort(int start,int end){                 //快速排序:手写版本
    if(start>=end)return;
    if(cutoff<=end-start+1){
        long pivot=median(start,end);
        int low=start,high=end-1;
        while(low<high){
            while(a[++low]<pivot);
            while(a[--high]>pivot);
            swap(&a[low],&a[high]);
        }
        swap(&a[low],&a[end-1]);
        mysort(start,low-1);
        mysort(low+1,end);
    }else sort(a,a+end-start+1);
}
//基数排序
#define maxdigit 4
#define radix 10
typedef struct node*pnode;
struct node{
    long key;pnode next;
};
struct headnode{
    pnode head,tail;
};
typedef struct headnode bucket[radix];
long factor;
int getdigit(long num,int bits){
    int bitnum;
    for(int i=0;i<bits;i++){
        bitnum=(int)num%radix;
        num/=radix;
    }
    return bitnum;
}
void mysort(int start,int end){                 //基数排序:LSD(次位优先)版本
    for(int i=0;i<n;i++)if(factor+a[i]<0)factor=-a[i];
    for(int i=0;i<n;i++)a[i]+=factor;
    bucket buk;
    pnode list=nullptr,p,tmp;
    for(auto&i:buk)i.head=i.tail=nullptr;
    for(int i=end-start;i>=0;i--){
        tmp=new struct node;
        tmp->key=a[i];
        tmp->next=list,list=tmp;
    }
    for(int i=1;i<=maxdigit;i++){
        p=list;
        while(p){
            int di=getdigit(p->key,i);
            tmp=p,p=p->next,tmp->next=nullptr;
            if(!buk[di].head)buk[di].head=buk[di].tail=tmp;
            else buk[di].tail->next=tmp,buk[di].tail=tmp;
        }
        list=nullptr;
        for(int j=radix-1;j>=0;j++){
            if(buk[j].head){
                buk[j].tail->next=list;
                list=buk[j].head;
                buk[j].head=buk[j].tail=nullptr;
            }
        }
    }
    for(int i=0;i<end-start+1;i++){
        tmp=list;
        list=list->next;
        a[i]=tmp->key-factor;
        free(tmp);
    }
}
void mysort_pass(int start,int end,int bits){
    bucket buk;
    pnode list=nullptr,p,tmp;
    if(bits<=0)return;
    for(auto&i:buk)i.head=i.tail=nullptr;
    for(int i=start;i<=end;i++){
        tmp=new struct node;
        tmp->key=a[i];
        tmp->next=list,list=tmp;
    }
    p=list;
    while(p){
        int di=getdigit(p->key,bits);
        tmp=p,p=p->next;
        if(!buk[di].head)buk[di].tail=tmp;
        tmp->next=buk[di].head,buk[di].head=tmp;
    }
    int left=start,right=start;
    for(auto i:buk){
        if(i.head){
            p=i.head;
            while(p){
                tmp=p,p=p->next;
                a[right++]=tmp->key;
                free(tmp);
            }
            mysort_pass(left,right-1,bits-1);
            left=right;
        }
    }
}
void mysort(int start,int end){                 //基数排序:MSD(主位优先)版本
    for(int i=0;i<end-start+1;i++)if(factor+a[i]<0)factor=-a[i];
    for(int i=0;i<end-start+1;i++)a[i]+=factor;
    mysort_pass(start,end,maxdigit);
    for(int i=0;i<end-start+1;i++)a[i]-=factor;
}    
int counts[radix];
long tmpa[maxcount];
void mysort(int start,int end){                 //基数排序:无链表版本
    int bits=1;
    for(int i=0;i<n;i++)if(a[i]+factor<0)factor=-a[i];
    for(int i=0;i<n;i++)a[i]+=factor;
    for(int i=0;i<maxdigit;i++){
        for(int&j:counts)j=0;
        for(int j=0;j<end-start+1;j++){
            int k=(int)(a[j]/bits)%radix;
            counts[k]++;
        }
        for(int j=1;j<radix;j++)counts[j]+=counts[j-1];
        for(int j=0;j<end-start+1;j++){
            int k=(int)(a[j]/bits)%radix;
            tmpa[counts[k]-1]=a[j];
            counts[k]--;
        }
        for(int j=0;j<end-start+1;j++)a[j]=tmpa[j];
        bits*=10;
    }
    for(int i=0;i<n;i++)a[i]-=factor;
}

统计工龄

给定公司N名员工的工龄,要求按工龄增序输出每个工龄段有多少员工。

输入格式

输入首先给出正整数N105N(≤10^5),即员工总人数;随后给出N个整数,即每个员工的工龄,范围在[0, 50]。

输出格式

按工龄的递增顺序输出每个工龄的员工个数,格式为:“工龄:人数”。每项占一行。如果人数为0则不输出该项。

输入样例

8
10 2 0 5 7 2 5 2

输出样例

0:1
2:3
5:2
7:1
10:1

ac代码

#include<iostream>
#define maxages 55
using namespace std;
int n,age,ages[maxages];
void count();
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>age;
        ages[age]++;
    }
    for(int i=0;i<maxages;i++)if(ages[i])cout<<i<<':'<<ages[i]<<endl;
}