7.简单排序算法、统计工龄
各种排序
给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果。本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下:
数据1:只有1个元素;
数据2:11个不相同的整数,测试基本正确性;
数据3:103个随机整数;
数据4:104个随机整数;
数据5:105个随机整数;
数据6:105个顺序整数;
数据7:105个逆序整数;
数据8:105个基本有序的整数;
数据9:105个随机正整数,每个数字不超过1000。
输入格式
输入第一行给出正整数,随后一行给出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名员工的工龄,要求按工龄增序输出每个工龄段有多少员工。
输入格式
输入首先给出正整数,即员工总人数;随后给出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;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 hetumessi's Blog!
评论
ValineGitalk