一.冒泡排序
原理:自左向右依次遍历,若相邻两数顺序错误,则交换两数.
这样,每一轮结束后,最大/最小的数就会到最后.
Code:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],in;
void PrintArray(int a[],int n){for(int i=1;i<=n;i++){printf("%d ",a[i]);}
}
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]); }for(int i=1;i<=n-1;i++){bool flag=true;for(int j=1;j<=n-1;j++){if(a[j]>a[j+1]) swap(a[j],a[j+1]),flag=false;} if(flag) break; } PrintArray(a,n);return 0;
}
我在此使用了函数.
二.选择排序
原理:自左向右依次遍历,选出最大/最小数,放到最前/最后
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1e5+1;
int n,a[N],in;
void PrintArray(int a[],int n){for(int i=1;i<=n;i++){cout<<a[i]<<" "; }
}
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]); }for(int i=1;i<=n-1;i++){in=i;for(int j=i+1;j<=n;j++){if(a[j]<a[in]){in=j; } } swap(a[in],a[i]);} PrintArray(a,n);return 0;
}
函数与双指针搭配,非常好用!
三.桶排序
桶排序是最快的排序.
每个数都对应了一个桶,遍历查找,若有该数,桶为true,最后遍历输出(并无真正排序)
但无法创建过多桶(数组爆炸危机)
Code:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],t,Max;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&t);a[t]=1;Max=max(Max,t); } for(int i=1;i<=Max;i++){if(a[i]) cout<<i<<" "; } return 0;
}
但如果一个数有两个呢?如:2个2
升级:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],t,Max;
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&t);a[t]++;Max=max(Max,t); } for(int i=0;i<=Max;i++){while(a[i]--) cout<<i<<" "; } return 0;
}
四.插入排序
插入排序,就是你打牌时摸牌并排序啦..
Code:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+1;
int n,a[N],in;
void PrintArray(int a[],int n){for(int i=1;i<=n;i++){cout<<a[i]<<" "; }
}
int main(){cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]); }for(int i=2;i<=n;i++){int in=i-1,now=i;while(in>=1 and a[now]<a[in]){swap(a[now--],a[in--]); } } PrintArray(a,n);return 0;
}
还有许多排序,等你去探索...
五.归并排序
#include <cstdio>
#include <malloc.h>#define maxn 1000001int a[maxn];void Input(int n, int *a) {for(int i = 0; i < n; ++i) {scanf("%d", &a[i]);}
}void Output(int n, int *a) {for(int i = 0; i < n; ++i) {if(i)printf(" ");printf("%d", a[i]);}puts("");
}void MergeSort(int *nums, int l, int r) {int i, mid, p, lp, rp;int *tmp = (int *)malloc( (r-l+1) * sizeof(int) ); // (1) if(l >= r) {return ; // (2) }mid = (l + r) >> 1; // (3) MergeSort(nums, l, mid); // (4) MergeSort(nums, mid+1, r); // (5) p = 0; // (6) lp = l, rp = mid+1; // (7) while(lp <= mid || rp <= r) { // (8) if(lp > mid) {tmp[p++] = nums[rp++]; // (9) }else if(rp > r) {tmp[p++] = nums[lp++]; // (10) }else {if(nums[lp] <= nums[rp]) { // (11) tmp[p++] = nums[lp++];}else {tmp[p++] = nums[rp++];}}}for(i = 0; i < r-l+1; ++i) {nums[l+i] = tmp[i]; // (12) } free(tmp); // (13)
}int main() {int n;while(scanf("%d", &n) != EOF) {Input(n, a);MergeSort(a, 0, n-1);Output(n, a);}return 0;
}
彩蛋:
求一数是否是完全平方数(int范围内)
bool sq(int a){return int(sqrt(a))*int(sqrt(a))==a;
} 需导入cmath头文件!
)
