C++数据排序( 附源码 )

一.冒泡排序

原理:自左向右依次遍历,若相邻两数顺序错误,则交换两数.

这样,每一轮结束后,最大/最小的数就会到最后.

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头文件!