7-13 統計工齡（20 分）
給定公司N名員工的工齡，要求按工齡增序輸出每個工齡段有多少員工。
輸入格式:
輸入首先給出正整數N（≤105），即員工總人數；隨後給出N個整數，即每個員工的工齡，範圍在[0, 50]。
輸出格式:
按工齡的遞增順序輸出每個工齡的員工個數，格式為：“工齡:人數”。每項佔一行。如果人數為0則不輸出該項。
輸入樣例:
8
10 2 0 5 7 2 5 2輸出樣例:
0:1
2:3
5:2
7:1
10:1（20 分）
給定公司N名員工的工齡，要求按工齡增序輸出每個工齡段有多少員工。
輸入格式:
輸入首先給出正整數N（≤105），即員工總人數；隨後給出N個整數，即每個員工的工齡，範圍在[0, 50]。
輸出格式:
按工齡的遞增順序輸出每個工齡的員工個數，格式為：“工齡:人數”。每項佔一行。如果人數為0則不輸出該項。
輸入樣例:
8
10 2 0 5 7 2 5 2輸出樣例:
0:1
2:3
5:2
7:1
10:1
1 #include<iostream>
2 using namespace std;
3 void swap(int &a,int &b){
4 int t=a; a=b; b=t;
5 }
6 void show_result(int A[],int N){
7 int cnt=0,age=A[0];
8 for(int i=0;i<N;i++){
9 if(A[i]==age) cnt++;
10 else {cout<<age<<":"<<cnt<<endl; age=A[i]; cnt=1;}
11 }
12 cout<<age<<":"<<cnt<<endl;
13 }
14 void Bubble_sort(int A[],int N){//冒泡排序法
15 for(int i=1;i<=N-1;i++){
16 int flag=0;
17 for(int j=0;j<=N-1-i;j++)
18 if(A[j]>A[j+1]) {flag=1; swap(A[j],A[j+1]);}
19 if(flag==0) break;
20 }
21 }
22 void Insertion_sort(int A[],int N){//插入排序法
23 int i,j;
24 for(i=1;i<N;i++){
25 int temp=A[i];
26 for(j=i;j>0;j--){
27 if(A[j-1]>temp) A[j]=A[j-1];
28 else break;
29 }
30 A[j]=temp;
31 }
32 }
33 void percdown(int A[],int N,int i){//最大堆下濾
34 int parent,child,temp=A[i];
35 for(parent=i;2*parent+1<=N-1;parent=child){
36 child=2*parent+1;
37 if(child<N-1&&A[child+1]>A[child]) child++;
38 if(temp<A[child]) A[parent]=A[child];
39 else break;
40 }
41 A[parent]=temp;
42 }
43 void buildheap(int A[],int N){//建立最大堆
44 for(int i=(N-1)/2;i>=0;i--){
45 percdown(A,N,i);
46 }
47 }
48 void heap_sort(int A[],int N){//堆排序
49 buildheap(A,N);
50 int size=N;
51 for(int i=1;i<=N-1;i++){
52 swap(A[0],A[size-1]);
53 percdown(A,--size,0);
54 }
55 }
56 void shell_sort(int A[],int N){//Sdegewick增量序列的希爾排序
57 int IncrementSequence_Sedgewick[]={0,
58 1,5,19,41,109,209,505,929,
59 2161,3905,8929,16001,36289,64769,146305,260609,
60 587521,1045505,2354689,4188161,9427969,16764929,37730305,67084289,
61 150958081,268386305,603906049,1073643521};
62 int i=1,len,j,k;
63 while(IncrementSequence_Sedgewick[++i]<=N){}
64 for(i=i-1;i>=1;i--){
65 len=IncrementSequence_Sedgewick[i];
66 for(j=len;j<N;j++){
67 int temp=A[j];
68 for(k=j;k>=len;k-=len)
69 {
70 if(temp<A[k-len]) swap(A[k],A[k-len]);
71 else break;}
72 A[k]=temp;
73 }
74 }
75 }
76 void Merge(int A[],int l,int r,int rend,int temp[]){
77 int lend=r-1,n=rend-l+1,cnt=l;
78 while(l<=lend&&r<=rend){
79 if(A[l]<A[r]) temp[cnt++]=A[l++];
80 else temp[cnt++]=A[r++];
81 }
82 while(l<=lend) temp[cnt++]=A[l++];
83 while(r<=rend) temp[cnt++]=A[r++];
84 for(int i=0;i<n;i++)
85 A[rend]=temp[rend--];
86 }
87 void Msort(int A[],int l,int rend,int temp[]){
88 int center;
89 if(l<rend){
90 center=(l+rend)/2;
91 Msort(A,l,center,temp);
92 Msort(A,center+1,rend,temp);
93 Merge(A,l,center+1,rend,temp);
94 }
95 }
96 void Merge_sort(int A[],int N){//歸併排序（遞歸）
97 int *temp;
98 temp=(int*)malloc(N*sizeof(int));
99 if(temp!=NULL){
100 Msort(A,0,N-1,temp);
101 free(temp);
102 }
103 else cout<<"there is no enough space!"<<endl;
104 }
105 void Merge1(int A[],int l,int r,int rend,int temp[]){
106 int lend=r-1,n=rend-l+1,cnt=l;
107 while(l<=lend&&r<=rend){
108 if(A[l]<A[r]) temp[cnt++]=A[l++];
109 else temp[cnt++]=A[r++];
110 }
111 while(l<=lend) temp[cnt++]=A[l++];
112 while(r<=rend) temp[cnt++]=A[r++];
113 }
114 void Merge_pass(int A[],int N,int len,int temp[]){
115 int i;
116 for(i=0;i<N-1-2*len;i+=2*len)
117 Merge1(A,i,i+len,i+2*len-1,temp);
118 if(i+len<N) Merge1(A,i,i+len,N-1,temp);
119 else
120 for(int j=i;j<N;j++) temp[j]=A[j];
121 }
122 void Merge_sort2(int A[],int N){//（非遞歸）歸併排序
123 int *temp;
124 temp=(int*)malloc(N*sizeof(int));
125 if(temp!=NULL){
126 int len=1;
127 while(len<N){
128 Merge_pass(A,N,len,temp);
129 len*=2;
130 Merge_pass(temp,N,len,A);
131 len*=2;
132 }
133 free(temp);
134 }
135 else cout<<"there is no enough space !"<<endl;
136 }
137 int getpivot(int A[],int l,int r){//獲得pivot
138 int m=(l+r)/2;
139 if(A[m]<A[l]) swap(A[m],A[l]);
140 if(A[r]<A[l]) swap(A[r],A[l]);
141 if(A[r]<A[m]) swap(A[r],A[m]);
142 swap(A[m],A[r-1]);
143 return A[r-1];
144 }
145 void Qsort(int A[],int l,int r){//快速排序遞歸核心算法
146 int pivot,i,j,cutoff=1000;
147 if(r-l>=cutoff){
148 int pivot=getpivot(A,l,r);
149 i=l; j=r-1;
150 while(1){
151 while(A[++i]<pivot) {}
152 while(A[--j]>pivot) {}
153 if(i<j) swap(A[i],A[j]);
154 else break;
155 }
156 swap(A[r-1],A[i]);
157 Qsort(A,l,i-1);
158 Qsort(A,i+1,r);
159 }
160 else Insertion_sort(A+l,r-l+1);
161 }
162 void Quick_sort(int A[],int N){// 快速排序
163 Qsort(A,0,N-1);
164 }
165 int main(){
166 int N; cin>>N;
167 int A[N];
168 for(int i=0;i<N;i++)
169 cin>>A[i];
170 //Bubble_sort(A,N);
171 //Insertion_sort(A,N);
172 //heap_sort(A,N);
173 //shell_sort(A,N);
174 //Merge_sort2(A,N);
175 Quick_sort(A,N);
176 show_result(A,N);
177 return 0;
178 }View Code
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
